ValidPalindrome [source code]

public class ValidPalindrome {
static
/******************************************************************************/
public class Solution {
    public boolean isPalindrome(String s) {
        char[] chs = s.toLowerCase().toCharArray();
        if (chs.length == 0) return true;
        int i = 0, j = chs.length - 1;
        while (i < j) {
            if (!Character.isLetter(chs[i]) && !Character.isDigit(chs[i])) {
                i++;
            } else if (!Character.isLetter(chs[j]) && !Character.isDigit(chs[j])) {
                j--;
            } else {
                if (chs[i++] != chs[j--]) return false;
                i++;
                j--;
            }
        }
        return true;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ValidPalindrome.Solution tester = new ValidPalindrome.Solution();
        String[] inputs = {
            "", "1",
            "abc", "0",
            "aba", "1",
            "A man, a plan, a canal: Panama", "1",
            "race a car", "0",
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            String s = inputs[2 * i];
            boolean expected = inputs[1 + 2 * i].equals("1");
            System.out.println(Printer.seperator());
            Printer.openColor("magenta");
            System.out.print(s);
            boolean output = tester.isPalindrome(s);
            Printer.closeColor();
            System.out.print(" -> " + output);
            Printer.openColor(output == expected ? "green" : "red");
            System.out.println(", expected: " + expected);
            Printer.closeColor();
        }
    }
}

没什么好说的简单题目, 这个都秒不掉就真的没办法说你了;

注意一个:

java> "a.b".toLowerCase()  
java.lang.String res0 = "a.b"

这个是无视非字母的entry的, 所以用起来不用担心;

判断字母和数字分别是isLetter和isDigit, 这个稍微要记住;

最后的速度是11ms (41%), 倒是不怎么出彩;

看了一下最优解, 最快的那个基本就是彻底不用Std API, 比如lowercase, Character这些. 这个看看就好了. 另外这里也侧面告诉你, 这些Std API其实并不是特别快, 面试被问到的话要有把握答出来;

这个是discussion里面一些人对于这个算法的header的看法:

I don't see any reason to enter the while loop when head = tail.
while(head < tail) should be enough.

反正实在不行, 你自己举个例子看看嘛, "abcba"这样的. 举例子的时候不要担心, "哎呀, 要是我这个例子没有代表性怎么办? 要是有反例怎么办?", 你别管他那么多, 你先把这个大众脸的例子举了并且能handle了再说, 然后再考虑是否有反例. 面试官是要看到你的进度的, 自己跟自己在脑子里绕弯子在面试官看来其实就是: 这个人是不是蠢?!

好像还有这么个API: Character.isLetterOrDigit.

不过让你自己写一个也不是什么难事;

另外我自己这个代码是可以继续concise的:

public class Solution {  
    public boolean isPalindrome(String s) {  
        char[] chs = s.toLowerCase().toCharArray();  
        if (chs.length == 0) return true;  
        int i = 0, j = chs.length - 1;  
        while (i < j) {  
            if (!Character.isLetter(chs[i]) && !Character.isDigit(chs[i])) i++;  
            else if (!Character.isLetter(chs[j]) && !Character.isDigit(chs[j])) j--;  
            else if (chs[i++] != chs[j--]) return false;  
        }  
        return true;  
    }  
}

没有直接在上面改, 还是想要跟你强调Premature Optmization的危害性, 脑子里不要总想着这个东西;

discussion基本也没有什么好的办法了, 毕竟题目本身也很简单;

Problem 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.

Difficulty:Easy
Total Accepted:164.9K
Total Submissions:632.1K
Contributor: LeetCode
Companies
microsoft uber facebook zenefits
Related Topics
two pointers string
Similar Questions
Palindrome Linked List