LC125 验证回文串 · 逐题动画 · RuntimeScope

RuntimeScope/算法实验台/56 天打卡/141 题/LC125

题型地图 56天全屏 141题

当前：LC125 · 验证回文串 · 首次出现于 Day 4 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC124 LC127 →

55 / 141回到 Day 4 卡片 141 题索引

LC125 · 验证回文串 · 工程执行实验室

过滤扫描舱 · 双指针原地比较

这题不是普通回文判断，而是在原字符串上跳过无效字符，只比较真正有效的字母数字字符。

下方「有效字符流」只是帮助理解过滤结果；真实代码不创建第二个字符串，双指针在原串上原地扫描，额外空间 O(1)。

主示例

"A man, a plan, a canal: Panama"

→ true

核心 · 原地过滤 + 双指针

这题不是普通回文判断，而是在原字符串上跳过无效字符，只比较真正有效的字母数字字符。

下方「有效字符流」只是帮助理解过滤结果；真实代码不创建第二个字符串，双指针在原串上原地扫描，额外空间 O(1)。

五步状态机

L=0, R=len(s)-1，从两端出发
while l < r && !isAlnum(s[l]) { l++ }
while l < r && !isAlnum(s[r]) { r-- }
lower(s[l]) != lower(s[r]) → false
相等则 l++, r--，继续向内收缩
l >= r → 全部有效字符已对称，true

跳过循环 · 必须 l < r

for l < r && !isAlnum(s[l]) { l++ }
for l < r && !isAlnum(s[r]) { r-- }

跳过循环必须写 while l < r && !isAlnum(...)。若字符串全是标点或空格，不判断 l < r 时指针可能越界，或在无效位置上重复移动。

边界案例实验台

切换样例会重算整段动画。观察跳过、比较与最终返回值。

当前样例：主示例期望 → true

1/34 · 读题

关键步骤：

Step 1读题理解过滤规则

读题：在原串上过滤有效字符

这题不是普通回文判断，而是在原字符串上跳过无效字符，只比较真正有效的字母数字字符。主示例：「A man, a plan, a canal: Panama」。

这题不是普通回文判断，而是在原字符串上跳过无效字符，只比较真正有效的字母数字字符。
下方「有效字符流」只是帮助理解过滤结果；真实代码不创建第二个字符串，双指针在原串上原地扫描，额外空间 O(1)。

为什么正确

下方「有效字符流」只是帮助理解过滤结果；真实代码不创建第二个字符串，双指针在原串上原地扫描，额外空间 O(1)。

机器状态 · L / R / 已确认对数

L	R	左有效	右有效	已确认	结果
0	29	a	a	0 对	—

当前动作

理解过滤规则

准备双指针扫描只看字母数字，标点空格全部跳过

双层视图 · 原串 + 概念有效流

空间 O(1) · 不创建第二个字符串

下方「有效字符流」只是帮助理解过滤结果；真实代码不创建第二个字符串，双指针在原串上原地扫描，额外空间 O(1)。

为什么正确 · 循环不变量

1.在任意时刻，L 左侧和 R 右侧已经被处理过的有效字符，都已经确认成对相等。
2.如果某次有效字符比较不相等，说明不可能是回文，立即 false。
3.如果两个指针相遇或交叉，说明所有需要比较的有效字符都已通过验证，返回 true。

Go · isPalindrome / isAlnum / lower

1func isAlnum(b byte) bool {
2    return (b >= 'a' && b <= 'z') ||
3        (b >= 'A' && b <= 'Z') ||
4        (b >= '0' && b <= '9')
5}
7func lower(b byte) byte {
8    if b >= 'A' && b <= 'Z' {
9        return b + 32
10    }
11    return b
12}
14func isPalindrome(s string) bool {
15    l, r := 0, len(s)-1
16    for l < r {
17        for l < r && !isAlnum(s[l]) {
18            l++
19        }
20        for l < r && !isAlnum(s[r]) {
21            r--
22        }
23        if l >= r {
24            break
25        }
26        if lower(s[l]) != lower(s[r]) {
27            return false
28        }
29        l++
30        r--
31    }
32    return true
33}

复杂度

时间: O(n)
空间: O(1)

每个下标最多被 L 或 R 访问一次。

只在原字符串上移动两个指针，不分配过滤后的新字符串。

面试怎么说

我用左右双指针从字符串两端向中间扫描。每次先跳过非字母数字字符，然后把左右两个有效字符统一转成小写比较。如果不相等立即返回 false；如果指针相遇或交叉，说明所有有效字符都对称，返回 true。整个过程每个字符最多访问一次，时间 O(n)，只使用常数额外空间。

常见误区

误区 1：只比较原字符，忘记忽略大小写

A 与 a 应视为相同，比较前需统一转成小写（或等价的大写转换）。

误区 2：跳过标点时忘记 l < r

跳过循环必须写 while l < r && !isAlnum(...)。若字符串全是标点或空格，不判断 l < r 时指针可能越界，或在无效位置上重复移动。

误区 3：把空字符串或全标点错误判成 false

没有有效字符需要比较时，L 与 R 会相遇或交叉，应返回 true。例如 " " 或 ".," 都是回文。

误区 4：先构造过滤字符串

先过滤再比较虽然能 AC，但额外用了 O(n) 空间；面试应强调原地双指针 O(1) 额外空间。