125. 验证回文串

Problem: 125. 验证回文串

思路

看到题目要求移除非字母数字字符后正反读一样，显然可以想到可以用相向双指针来做。对于不符合要求的字符，我们跳过即可，无需删除。

Java语法相关

Java里把字符转为小写有两种方法：

1. 将字符串中所有字符转为小写：string.toLowerCase()
2. 将一个字符转为小写：Character.toLowerCase(ch)

另外Java里还有判断字符是否为数字或者字符的方法：
Character.isLetterOrDigit(ch)
Java的Character类功能是很丰富的。

复杂度

• 时间复杂度: $O(n)$。
• 空间复杂度: $O(n)$，n为字符串长度。

Code

[]

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