验证回文串为什么适合用相向双指针？如何跳过非字母数字字符？

简化版

验证回文串用左右指针从两端向中间扫：左边遇到非字母数字就右移，右边遇到非字母数字就左移，两个有效字符统一转小写后比较。每个字符最多被访问一次，所以时间复杂度是 O(n)，额外空间 O(1)。

详细版

这题的关键不是“反转字符串再比较”，而是利用回文的对称性。左指针 l 从 0 开始，右指针 r 从 n - 1 开始；当 s[l] 不是字母数字时，l++；当 s[r] 不是字母数字时，r--；两边都有效时比较 lower(s[l]) 和 lower(s[r])，不同则直接返回 false，相同则继续收缩。

示例 "A man, a plan, a canal: Panama" 忽略空格和标点后是 "amanaplanacanalpanama"，左右对称，所以是回文。若输入 "race a car"，有效字符比较到 e 和 a 时不相等，返回 false。

面试要说清楚三个边界：空串或只有标点时应返回 true；大小写要统一；循环条件通常是 while (l < r)，不要在指针交叉后继续访问。

完整版教学

一、为什么这题是相向双指针

回文的定义是“从左往右读”和“从右往左读”一致，所以天然对应两个端点同时向中间靠拢。暴力做法可以先过滤出新字符串再反转比较，但这会额外分配 O(n) 空间；相向双指针把“过滤”和“比较”合在一次扫描里完成。

看一个长度为 30 的字符串，如果只有 21 个有效字符，构造新串仍要额外存 21 个字符。双指针则只维护 l、r 两个下标，遇到无效字符就跳过，不改变问题本质。

原串: A  _  m  a  n  ,  ...
      l                         r
动作: 非字母数字 -> 跳过；有效字符 -> 小写比较

记忆钩子：回文题先想“镜像位置是否相等”，镜像位置一出现，左右指针通常比额外构造字符串更稳。

二、有效字符过滤是算法的一部分

题目通常要求只考虑字母和数字，并忽略大小写。很多错误写法会先比较再跳过标点，导致 ','、空格、':' 参与比较，结果被误判。

正确顺序是：先让左指针停在有效字符上，再让右指针停在有效字符上，最后才比较。以 "A, a" 为例，l=0 是 A，r=3 是 a，比较小写相等；中间的逗号和空格都不会进入比较逻辑。

while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false;

三、指针移动的不变式

双指针正确性的核心是不变式：每一轮比较前，[0, l) 和 (r, n-1] 中所有需要比较的有效字符已经完成匹配，剩下只需要判断 l..r。如果当前两端有效字符相等，就可以安全丢弃这两个字符，因为它们已经满足回文约束。

举例："ab@ba"。第一轮 a == a，问题缩成 "b@b"；跳过 @ 后比较 b == b，问题继续缩小。每轮都让未验证区间变短，最终指针相遇或交叉时，说明所有镜像字符都匹配。

[已验证] l .... r [已验证]
相等后:
[已验证更多] l .. r [已验证更多]

四、代码模板与边界

面试时推荐写成一个循环，内部先跳过无效字符，再比较有效字符。这样逻辑集中，边界也容易控制。

boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
        while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
        char a = Character.toLowerCase(s.charAt(l));
        char b = Character.toLowerCase(s.charAt(r));
        if (a != b) return false;
        l++;
        r--;
    }
    return true;
}

空串、单字符、全标点都会自然返回 true。例如 "!!!" 会一直跳过，最后 l >= r，没有发现任何矛盾。

五、复杂度和方案对比

方案	时间复杂度	额外空间	面试评价
过滤新串再反转	O(n)	O(n)	容易写，但没有体现原地扫描
栈保存一半字符	O(n)	O(n)	对这题偏重
相向双指针	O(n)	O(1)	最推荐，边界清楚

O(n) 的原因是每个指针只朝一个方向移动。即使有很多标点，字符也只会被左指针或右指针跳过一次，不会反复扫描。

六、常见误区与追问

误区：先比较字符再判断是不是字母数字。 这样会把空格、逗号、冒号当成有效内容，典型样例会误判。
误区：只忽略空格，不忽略标点。 题目说的是非字母数字都忽略，标点也要跳过。
误区：忘记统一大小写。 A 和 a 在这题中应视为相等。
追问：为什么全是标点时返回 true？ 因为过滤后有效字符序列为空，空序列满足回文定义。
追问：这题和最长回文子串有什么区别？ 验证回文是检查整体序列，最长回文子串要枚举中心或做动态规划，目标不同。
追问：Unicode 字符怎么办？ 面试默认按语言库的字母数字判断；如果业务有多语言规范，要明确字符集和大小写折叠规则。

七、手推一个完整例子

以 "0P" 为例，l=0 是数字 0，r=1 是字母 P，两者都是有效字符；统一小写后仍是 0 和 p，不相等，返回 false。

再看 "A man, a plan" 的前几步：A 对 n 不相等，所以它不是回文；这能说明算法不是“看到常见句式就返回 true”，而是真正按镜像字符验证。

s = "race a car"
l=0 r=9: r == r -> l=1 r=8
l=1 r=8: a != a? 相等 -> l=2 r=7
l=2 r=7: c != c? 相等 -> l=3 r=6
l=3 r=6: e vs a -> false

八、加强记忆

把验证回文记成三步：先让左右指针站到“有效字符”上，再把大小写规整到同一标准，最后比较镜像字符。镜像相等就一起收缩，镜像不等就立刻失败。复杂度的锚点是“每个字符最多被跳过或比较一次”，边界的锚点是“指针交叉代表没有矛盾”。

简化版

详细版