Difficulty: Easy · LeetCode 125

Problem

Determine if a string is a palindrome considering only alphanumeric characters and ignoring cases.

Understanding the problem

Ignore spaces and punctuation; check if string equals its reverse.

Intuition

Use two pointers converging inward from left and right ends, skipping non-alphanumeric characters in O(1) space.

Approach

Initialize left = 0, right = len(s) - 1.
Advance left while not s[left].isalnum().
Decrement right while not s[right].isalnum().
Compare lowercased characters. If match, move both pointers inward.

Naive Solution — Brute Force

Filter alphanumeric characters into a new string and reverse it.

Python

class Solution:
    def isPalindrome(self, s):
        cleaned = ""

        for char in s:
            if char.isalnum():
                cleaned += char.lower()

        return cleaned == cleaned[::-1]

C++

class Solution {
public:
    bool isPalindrome(string s) {
        string cleaned;
        for (char c : s)
            if (isalnum((unsigned char)c)) cleaned += tolower((unsigned char)c);
        return cleaned == string(cleaned.rbegin(), cleaned.rend());
    }
};

Java

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder cleaned = new StringBuilder();
        for (char c : s.toCharArray())
            if (Character.isLetterOrDigit(c)) cleaned.append(Character.toLowerCase(c));
        String str = cleaned.toString();
        return str.equals(cleaned.reverse().toString());
    }
}

JavaScript

var isPalindrome = function(s) {
    let cleaned = "";
    for (const c of s)
        if (/[a-z0-9]/i.test(c)) cleaned += c.toLowerCase();
    return cleaned === cleaned.split("").reverse().join("");
};

Time: O(n) · Space: O(n)

Optimized Code (Python 3)

Python

class Solution:
    def isPalindrome(self, s):
        left = 0
        right = len(s) - 1

        while left < right:

            while left < right and not s[left].isalnum():
                left += 1

            while left < right and not s[right].isalnum():
                right -= 1

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True

C++

class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right) {
            while (left < right && !isalnum((unsigned char)s[left])) left++;
            while (left < right && !isalnum((unsigned char)s[right])) right--;
            if (tolower((unsigned char)s[left]) != tolower((unsigned char)s[right]))
                return false;
            left++;
            right--;
        }
        return true;
    }
};

Java

class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right)))
                return false;
            left++;
            right--;
        }
        return true;
    }
}

JavaScript

var isPalindrome = function(s) {
    const isAlnum = c => /[a-z0-9]/i.test(c);
    let left = 0, right = s.length - 1;
    while (left < right) {
        while (left < right && !isAlnum(s[left])) left++;
        while (left < right && !isAlnum(s[right])) right--;
        if (s[left].toLowerCase() !== s[right].toLowerCase()) return false;
        left++;
        right--;
    }
    return true;
};

Time: O(n) · Space: O(1)

Takeaway

Pattern — Inward converging Two Pointers