Valid Palindrome

Share

Given a string s, return true if it is a palindrome considering only alphanumeric characters and ignoring case.

Example 1
Input: "A man, a plan, a canal: Panama" → Output: true
Example 2
Input: "race a car" → Output: false

Solution Approach

Two pointers from both ends. Skip non-alphanumeric characters. Compare lowercase versions of characters at both pointers.

  • lo=0, hi=s.length()-1.
  • While lo
  • Compare Character.toLowerCase(s[lo]) with s[hi].
  • If mismatch return false; else lo++, hi--.
Java
class Solution {
    public boolean isPalindrome(String s) {
        int lo = 0, hi = s.length() - 1;
        while (lo < hi) {
            while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) lo++;
            while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) hi--;
            if (Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi)))
                return false;
            lo++; hi--;
        }
        return true;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(1)