125. Valid Palindrome

Description

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

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

Constraints

• s consists only of printable ASCII characters.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: "A man, a plan, a canal: Panama"

Output: true

Example 2

Input: "race a car"

Output: false

Solutions

Solution 1

/**
 * Time complexity : O(N)
 * Space complexity : O(1)
 */

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

Follow up