每日算法 验证回文串

例题：125. 验证回文串

题目描述：

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

代码：

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sbuilder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);   //将字符串地址为i的字符转移成char类型以便赋值给c
            if (Character.isLetterOrDigit(c)) {
                sbuilder.append(Character.toLowerCase(c));
            }
        }
        //用双指针判断筛掉空格和符号的剩余字符串是否是回文
        int left = 0;
        int right = sbuilder.length() - 1;
        while (left < right) {
            if (sbuilder.charAt(left) != sbuilder.charAt(right)) {
                return false;
            }
            left ++;
            right --;
        }
        return true;
    }
}

思路：

将原内容里面的空格和符号都筛选掉得到一个只有字母和数字的纯净字符串就行了。这里面要先将 String字符串 中的内容每一个单独挑出来去做检测（也就是用下标遍历并用 charAt() 转换成 char 类型去进行检测），调用 Java 中自带的类 isLetterOrDigit() 去检测内容是否为字母或者数字，如果是的话把内容加进一个自由变换的字符串中，也就是 StringBuilder 对象。

然后将筛选完的字符串用正常的字符串回文的方法 双指针 去进行判断就行。

这题其实做过回文的话，不懂的地方可能就在 Java 的 StringBuilder 对象的用法和那个检测数字和字母的方法。

补充：

官方题解里面有在原字符串上直接进行判断的，相比于上面这种做法，少了一个字符转换的 while 循环，运行快，且只使用了 O(1) 的空间。让我们来看看下面的代码进行一下简单的区别分析：

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int left = 0, right = n - 1;
        //一个循环里面做完所有事
        while (left < right) {
            //通过下面两个循环进行跳过非数字和字母的其他内容，当左边遇到非数字和字母就++跳过，是数字和字母就和右边进行比较（右边也是和左边一样的流程，只不过是--跳过）
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                ++left;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                --right;
            }
            if (left < right) {
                //左右比较是否相等，不等则不成立回文
                if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                    return false;
                }
                //这里的++和--是比较完之后的++和--，与前面的遇到非数字和字母的++、--是不一样的原因
                ++left;
                --right;
            }
        }
        return true;
    }
}