10. Valid Palindrome · DSA Practice

Ignoring case and every character that is not a letter or digit, does s read the same forwards and backwards?

Example 1

Input: s = "Was it a car, or a cat I saw?"

Output: true

Example 2

Input: s = "race a car"

Output: false

Hint 1

Put one pointer at each end and walk them toward each other, skipping non-alphanumeric characters.

Two PointersString

Approach 1: Clean and reverse

Build a cleaned lowercase string and compare it with its reverse.

⏱ Time O(n)💾 Space O(n)

Approach 2: Two pointers ✅

Compare from both ends in place, skipping junk characters.

⏱ Time O(n)💾 Space O(1)

Reference solution for Two pointers (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        while i < j:
            if not s[i].isalnum():
                i += 1
            elif not s[j].isalnum():
                j -= 1
            elif s[i].lower() != s[j].lower():
                return False
            else:
                i += 1
                j -= 1
        return True

class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            char a = s.charAt(i), b = s.charAt(j);
            if (!Character.isLetterOrDigit(a)) i++;
            else if (!Character.isLetterOrDigit(b)) j--;
            else if (Character.toLowerCase(a) != Character.toLowerCase(b)) return false;
            else { i++; j--; }
        }
        return true;
    }
}

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

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

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

This problem is explained in the lesson Two Pointers.