如何实现回文串判断算法？

回文串是正读和反读都一样的字符串。我们可以使用双指针法实现回文串判断算法:

public boolean isPalindrome(String s) {
    s = s.toLowerCase();
    s = s.replaceAll("[^a-zA-Z0-9]", "");

    int i = 0;
    int j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i) != s.charAt(j)) return false;
        i++;
        j--;
    }
    return true;
}

算法流程:

1. 将字符串转为小写,并去除非字母和数字的字符。得到规范后的字符串 s。
2. 对 s 的两头设置左右指针 i 和 j。
3. 比较 i 和 j 指向的字符,如果相等则同时移动 i 和 j。
4. 如果不相等,则 s 不是回文串,返回 false。
5. 如果指针 i 与 j 重合或交叉,则比较完成,s 是回文串,返回 true。

时间复杂度 O(n),空间复杂度 O(1)。

所以,回文串判断的关键是:

1. 规范化字符串,转小写并去除非字母和数字字符。
2. 设置左右指针,从两头向中间比较字符。
3. 若字符相等则同时移动指针,若不相等则不是回文串,返回false。
4. 指针重合代表比较完成,是回文串,返回true。