125.md

125. Valid Palindrome

Description

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example, "A man, a plan, a canal: Panama" is a palindrome. "race a car" is not a palindrome.

Note: Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

Thinking Process

1. Use two pointers, low, high pointing to the head and the tail of the string respectively
2. Skip if s[low] or s[high] is not alphanumeric
3. If s[low] != s[high], return false

Code

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

Complexity

1. Time complexity is O(n) as the string is only scanned once