Valid Palindrome

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

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.

Example:

"A man, a plan, a canal: Panama" is a palindrome.

"race a car" is not a palindrome.

Challenge:

O(n) time without extra memory.

Solution:

This problem is not hard, however, there are few things need to consider:

1. ".,.;';'[]": this should be considered as empty string, because there is no letters or digits
2. "*&%abccba|||))" should be considered as valid palindrome
3. "321123": digits should be considered as same as characters, so this is valid palindrome

Code:

public class Solution {
    /**
     * @param s A string
     * @return Whether the string is a valid palindrome
     */
    public boolean isPalindrome(String s) {
        if (s == null || s.length() <= 1) {
            return true;
        }
        int left = 0;
        int right = s.length() - 1;
        while (left < right) {
            while (left < s.length() && !isValid(s.charAt(left))) {
                left++;
            }
            if (left == s.length()) {
                return true;
            }
            while (right >= 0 && !isValid(s.charAt(right))) {
                right--;
            }

            if (!isSame(s.charAt(left), s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

In addition, we could find all the possible sub-palindromes by following dynamic programming code:

public class Solution {
    /**
     * @param s A string
     * @return Whether the string is a valid palindrome
     */
    public boolean isPalindrome(String s) {
        // Write your code here
        if (s == null || s.length() == 0) {
            return true;
        }
        s = s.toLowerCase();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (isValid(c)) {
                sb.append(c);
            }
        }
        String newS = sb.toString();
        if (newS.length() > 0) {
            boolean[][] p = getPalindrome(newS);
            return p[0][newS.length() - 1];
        } else {
            return true;
        }
    }

    private boolean isValid(char c) {
        return Character.isLetter(c) || Character.isDigit(c);
    }

    private boolean isSame(char a, char b) {
        return Character.toLowerCase(a) == Character.toLowerCase(b); 
    }

    public boolean[][] getPalindrome(String s) {
        //assume s.length() > 0
        int n = s.length();
        //state: f[x][y] represents the substring (x, y) is palindrome or not
        boolean[][] f = new boolean[n][n];
        //initialization: 
        //  case i: when length is 0, e.g. f[0][0], f[x][x] is always palindrome
        for (int i = 0; i < n; i++) {
            f[i][i] = true;
        }
        // case ii: when length is 1, e.g. f[1][2], f[x][x+1] depends on equivalence of s[1] and s[2]
        for (int i = 0; i < n - 1; i++) {
            f[i][i + 1] = isSame(s.charAt(i), s.charAt(i + 1));
        }
        //function:
        /*
        *  AxxxxB depends on the equivalence of A and B AND xxxx is palindrome
        * f[i][j] = f[i][j - 1] && (s.charAt(i) == s.charAt(j))
        */
        for (int length = 2; length < n; length++) {
            for (int start = 0; start + length < n; start++) {
                f[start][start + length] = 
                    f[start + 1][start + length - 1] && (s.charAt(start) == s.charAt(start + length));
            }
        }
        //answer
        return f;
    }
}