Valid Palindrome

Question

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

Notice

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.

Tags

String Two Pointers Facebook Zenefits Uber

Related Problems

Medium Palindrome Linked List Medium Longest Palindromic Substring

Analysis

根据Palindrome本身对称性的特点，比较适合用two pointers的方法来解决，因为这里对valid palindrome的定义不考虑非字母和数字的字符，就需要在移动pointers时候注意条件判断，除了下标的边界，还有isAlphanumeric()来判定是否为字母和数字。isAlphanumeric()可以用内置函数Character.isLetter()和Character.isDigit()，也可以根据char ASCII码的定义写出。补充：还有一个专门内置函数：Character.isLetterOrDigit()，用Character.toLowerCase()统一大小写。

Test Cases需要考虑周到，比如：

" " "a..." "...a" "a.a"

Solution

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() == 0) {
            return true;
        }
        int i = 0;
        int j = s.length() - 1;

        while (i < j) {
            while (i < s.length() && !isAlphanumeric(s.charAt(i))) {
                i++;
            }
            if (i == s.length()) {
                return true;
            }
            while (j >= 0 && !isAlphanumeric(s.charAt(j))) {
                j--;
            }

            if (Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j))) {
                break;
            } else {
                i++;
                j--;
            }
        }
        return (j <= i);
    }

    public boolean isAlphanumeric(char ch) {
        // return Character.isLetter(ch) || Character.isDigit(ch);
        boolean result = (ch <= 'z' && ch >= 'a') ||
            (ch <= 'Z' && ch >= 'A') ||
            (ch <= '9' && ch >= '0');
        return result;

    }
}

Another implementation of isAlphanumeric()

    // Use Character methods isLetter(), isDigit()
    private boolean isAlphanumeric (char c) {
        return Character.isLetter(c) || Character.isDigit(c);
    }

A verbose way - filter alphanumeric first, then start expanding from middle point of the new string

Time - O(n), Space O(n)

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (Character.isLetter(ch)) {
                sb.append(Character.toLowerCase(ch));
            } else if (Character.isDigit(ch)) {
                sb.append(ch);
            }
        }

        String t = sb.toString();
        System.out.println(t);

        int i, j;

        if (t.length() % 2 == 0) {
            // even number
            i = (t.length() - 1) / 2;
            j = i + 1;

        } else {
            // odd number
            i = t.length() / 2;
            j = i;
        }
        while (i >= 0 && j < t.length()) {
            if (t.charAt(i) != t.charAt(j)) {
                return false;
            }
            i--;
            j++;
        }

        return true;
    }
}

*(Preferred) A concise, one pass (4ms, 92.32%)

善用Character.isLetterOrDigit()函数，跳过非alphanumeric的字符，然后在比较时，用Character.toLowerCase()统一大小写。

class Solution {
    public boolean isPalindrome(String s) {
        int l = 0;
        int r = s.length() - 1;
        while (l < r) {
            char lChar = s.charAt(l);
            char rChar = s.charAt(r);
            if (!Character.isLetterOrDigit(lChar)) {
                l++;
            } else if (!Character.isLetterOrDigit(rChar)) {
                r--;
            } else {
                if (Character.toLowerCase(lChar) != Character.toLowerCase(rChar)) {
                    return false;
                }
                l++;
                r--;
            }
        }
        return true;

    }
}

Reference

http://www.jiuzhang.com/solutions/valid-palindrome/