LC125Easy字符串双指针原地扫描

验证回文串

先忽略空格和标点，把大小写统一，再让左右两位字符检查员从两端寻找下一对有效字符。

题目是什么

忽略非字母数字字符和大小写后，判断字符串是否正反相同。

解决什么问题

在原字符串上完成过滤与比较，避免额外创建新字符串。

核心结论

左右跳过无效字符，统一小写比较；相等收缩，不同立即失败。

01交互算法精讲

先说结论：这道题到底解决什么

原字符串里混有空格、标点和大小写差异，怎样不创建过滤副本，就让左右指针每次都比较“有效字符流”最外侧的一对字符？

中心结论：左右跳过无效字符，统一小写比较；相等收缩，不同立即失败。

读完必须能回答
  1. 1.题目真正判断的是原字符串，还是过滤并统一大小写后的有效字符序列？
  2. 2.左右指针怎样安全跳过无效字符，并且不会在全标点输入上越界？
  3. 3.为什么每个字符只会被指针经过一次，双指针仍然是 O(n) 而不是 O(n²)？
02交互算法精讲

完整题目与题意拆解

给定字符串 s，如果把所有大写字母转换成小写、删除所有非字母数字字符后，字符串正读和反读相同，就返回 true。

字母数字字符包括 a-z、A-Z 和 0-9。数字不能被当成标点跳过。

  • • 空字符串或全部由标点组成的字符串返回 true。
  • • 大小写不敏感，但大写字母仍参与比较。
  • • 题目字符范围适合用 Go byte 处理 ASCII。
输入：s = "A man, a plan, a canal: Panama"
输出：true
解释：处理后得到 "amanaplanacanalpanama"。

输入：s = "race a car"
输出：false

题目判断的不是原句表面，而是“保留字母数字、统一大小写”后的有效字符序列。

教学时可以先想象过滤后的字符串，但最优实现不需要真的创建它。双指针能在原字符串上边找边比较。

短样例 " A, b a!" 的有效字符是 "Aba"，忽略大小写后是 "aba"，所以答案为 true。
动画 1 · 题意扫描

真正要比较的字符串是哪一个

原字符串与下方规范化有效流同步出现，标点淡出、字母统一小写，先建立准确的判断对象。

Step 1/20%
输入：" A, b a!"
␠
0
A
1
,
2
␠
3
b
4
␠
5
a
6
!
7
有效字符流：A b a
看完带走：回文判断针对过滤且规范化后的有效字符流。
03交互算法精讲

第一层方案：暴力做法

第一版可以遍历字符串，把所有字母数字转成小写后写入新切片，再用反转或双指针检查新切片。

它时间是 O(n)，空间也是 O(n)。这是很好的题意验证版本，但面试通常期待原地双指针把额外空间降到 O(1)。

filtered := []byte{}
for each c in s:
  if isAlnum(c): append(toLower(c))
return filtered == reverse(filtered)
优化的核心不是少扫描一次，而是不再保存完整过滤结果。
动画 2 · 暴力重复

先构造新字符串的代价

演示把所有有效字符复制到新数组再比较的直观方案，并突出它额外占用与输入等长的空间。

Step 1/30%
输入：" A, b a!"
␠
0
A
1
,
2
␠
3
b
4
␠
5
a
6
!
7
有效字符流：A b a
看完带走：过滤副本容易理解，但会使用 O(n) 额外空间。

优化方向：两端字符天然成对。只要指针能够跳过无效字符，就可以在原字符串上完成同样判断。

04交互算法精讲

整体地图：先做什么，再做什么

先把判断对象从原字符串改写为“只保留字母和数字、忽略大小写后的有效字符流”。教学上可以想象先得到过滤串，但生产代码无需真的分配它。

左右指针从原字符串两端出发，各自跳过无效字符；找到有效字符后统一成小写比较。相同则同时收缩，不同立即失败，直到指针相遇。

  • • 跳过无效字符是在原串上惰性构造有效流。
  • • 数字也是有效字符，不能只判断字母。
  • • 两侧跳过循环都必须带 l<r 边界。
双指针不是直接比较原串两端，而是在按需发现有效字符流的两端。
05交互算法精讲

在原字符串上惰性读取规范化后的有效字符流

如果显式过滤，可以得到一个只含字母数字且全部小写的新字符串，再检查它是否回文。这很直观，但需要 O(n) 额外空间。

双指针把过滤过程推迟到真正需要字符时：左指针寻找下一个有效字符，右指针寻找上一个有效字符。此时它们恰好对应剩余有效流最外侧的一对。

“A man, a plan, a canal: Panama” 的首轮有效比较是 A 与 a，而不是直接拿 A 与最后一个标点或空格比较。
跳过不是丢失信息，因为被跳过的字符本来就不属于题目定义的判断对象。
动画 3 · 核心概念

双指针惰性发现有效流两端

左右指针在原字符串上越过灰色无效字符，只在碰到有效字符时停下并形成一对。

Step 1/30%
L=0 · R=7
L
␠
0
A
1
,
2
␠
3
b
4
␠
5
a
6
!
R
两端当前都不是字母数字
看完带走：无需创建副本，也能读取有效字符流的最外侧。
06交互算法精讲

左跳过、右跳过、规范化比较、同时收缩

外层循环保持 l<r。左侧 while 在 l<r 且 s[l] 不是字母数字时递增 l；右侧对称地递减 r。两个跳过循环结束后，再将 s[l] 与 s[r] 统一小写比较。

若不同立即返回 false；若相同则 l++、r--。循环结束说明有效流剩余零个或一个字符，天然满足回文，返回 true。

  • • isAlnum 必须覆盖 a-z、A-Z 和 0-9。
  • • toLower 只转换大写字母，数字和小写字母保持不变。
  • • 每个指针单向移动，不会回头重复扫描。
  • • 空字符串或全标点会让指针相遇并正确返回 true。

初始化 l=0、r=len(s)-1。只要 l<r，就分别跳过两端无效字符，然后比较 toLower(s[l]) 与 toLower(s[r])。

不同返回 false；相同则 l++、r--。循环结束表示所有需要比较的字符对都通过，返回 true。

当有效字符流为空或只剩一个字符时，指针会相遇或交叉。没有任何不匹配字符对，因此结果是 true。
动画 4 · 机制构建

跳过、比较、收缩的固定循环

四个动作按相同节奏重复，当前字符、规范化结果与指针下一位置始终同步显示。

Step 1/40%
寻找下一对有效字符
␠
0
L
A
1
,
2
␠
3
b
4
␠
5
a
R
!
7
L: 0 → 1 · R: 7 → 6
看完带走：固定四步模板能同时保证安全边界和清晰状态。
07交互算法精讲

为什么跳过和两端收缩不会改变答案

循环不变量是：已经越过的有效字符都已成对相等，l 与 r 之间包含尚未验证的有效字符流。跳过的标点和空格不属于有效流，所以移动指针不会改变待验证对象。

跳过结束后，s[l] 与 s[r] 是待验证有效流最外侧的一对。规范化后若不同，任何内部字符都无法修复最外侧不相等，立即返回 false 正确。

若相等，删除这对外侧字符后，原问题等价于更短的内部有效流。不断收缩到零或一个字符时，剩余部分必为回文。

正确性来自每轮都准确找到并消去有效流的最外侧一对。
正确性抓手
  • • 跳过循环移除的字符不属于题目定义的有效序列，因此不会改变答案。
  • • 每轮比较的正是剩余有效序列最外侧的一对字符。
  • • 相等后去掉这一对保持问题等价；不同则必定不是回文。
08交互算法精讲

完整执行过程

短样例只保留 8 个字符，让每一步移动都可见。请重点观察 L/R 的旧位置和新位置，以及被跳过字符为什么不参与比较。

  1. 1l 指向开头 A，r 从末尾开始跳过无效字符，落在最后的 a。
  2. 2A 和 a 统一为小写后相等，两侧指针同时向中间移动。
  3. 3左侧依次跳过空格，右侧跳过标点与空格，再找到下一对有效字符。
  4. 4重复比较并收缩，所有外侧有效字符对都相等。
  5. 5指针相遇，未发现冲突，返回 true。
动画 5 · 完整执行

从外到内完成经典示例

完整播放有效字符对逐个匹配直到指针相遇，再切换到 race a car 展示第一次不匹配如何立即结束。

Step 1/50%
第一对通过
␠
0
L
A
1
,
2
␠
3
b
4
␠
5
a
R
!
7
A → a，a == a
看完带走：外侧一旦不同即可失败，全部成对相同才成功。
09交互算法精讲

把动画和 Go 代码逐行对应

每一帧使用稳定的语义行 ID，不依赖容易漂移的数字行号。先观察分支为什么成立， 再看对应代码，而不是先背模板。

动画 6 · 代码映射

Go 边界判断如何避免越界

高亮两个带 l<r 的跳过循环、isAlnum 的数字分支和 toLower，让代码状态与指针位置逐步绑定。

Step 1/40%
寻找下一对有效字符
␠
0
L
A
1
,
2
␠
3
b
4
␠
5
a
R
!
7
L: 0 → 1 · R: 7 → 6
看完带走：边界条件和有效字符定义共同决定实现是否可靠。
Step 1
先分清哪些字符参与比较

题目只保留字母和数字，并忽略大小写。

func · init-pointers
Step 2
两位检查员从两端就位

指针先站在边界，再各自寻找下一位有效字符。

init-pointers · outer-loop
Step 3
跳过两端噪声

空格和感叹号不是字母数字，不影响处理后的字符序列。

skip-left · move-left · skip-right · move-right
Step 4
A 按 a 比较，这一对相等

忽略大小写不是跳过大写，而是转换到同一比较形式。

compare-normalized · shrink-left · shrink-right
Step 5
内部标点仍按同一规则跳过

规则不会因字符位于字符串内部而改变，非字母数字始终不参与比较。

skip-left · move-left · skip-right · move-right
Step 6
指针相遇，外侧字符对全部通过

中间单个字符无需和自己比较；没有发现任何不匹配字符对。

outer-loop · return-true
Step 7
失败样例在第一处不同立即结束

回文要求所有镜像字符对相等，一处不同足以证明整串失败。

compare-normalized · return-false
Step 8
空有效流为 true，数字必须参与

空序列正反相同，而 0 属于有效数字，不能忽略。

is-alnum · digit-check · return-true
Step 9
跳过、跳过、比较、收缩

每个字符最多被指针经过一次，不创建过滤字符串。

skip-left · skip-right · compare-normalized · return-true
10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法
1func isPalindrome(s string) bool {2    l, r := 0, len(s)-13    for l < r {4        for l < r && !isAlnum(s[l]) {5            l++6        }7        for l < r && !isAlnum(s[r]) {8            r--9        }10        if toLower(s[l]) != toLower(s[r]) {11            return false12        }13        l++14        r--15    }16    return true17}18 19func isAlnum(c byte) bool {20    return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9'21}22 23func toLower(c byte) byte {24    if c >= 'A' && c <= 'Z' {25        return c + ('a' - 'A')26    }27    return c28}
最小测试集合
// 忽略标点与大小写
fmt.Println(isPalindrome("A man, a plan, a canal: Panama")) // true
// 第一组不匹配字符决定失败
fmt.Println(isPalindrome("race a car")) // false
// 空有效流天然是回文
fmt.Println(isPalindrome(" ")) // true
// 数字必须参与比较
fmt.Println(isPalindrome("0P")) // false
11交互算法精讲

正确性与复杂度

时间复杂度 O(n)

左右指针只向中间移动，每个字符最多被检查常数次，不会来回扫描。

空间复杂度 O(1)

只保存 l、r 和少量 byte 变量，不创建与输入长度相关的新字符串。

12交互算法精讲

最容易写错的地方

错误 1

直接比较原字符串，没有跳过空格和标点。

错误 2

isAlnum 忘记包含 0-9。

错误 3

跳过循环漏掉 l < r，在全标点输入上越界。

错误 4

大小写转换写死 32，降低可读性和可移植性。

错误 5

把双指针移动误判成 O(log n)。

13交互算法精讲

最后复盘：带走逻辑链

  1. 1.先分清有效字符，再讨论回文。
  2. 2.四步模板：左跳过、右跳过、比较、收缩。
  3. 3.空有效流和单字符天然为 true。
  4. 4.教学过滤串帮助理解，生产解法保持 O(1) 额外空间。
面试表达
  1. 1.先说明判断对象：只保留字母数字并忽略大小写。
  2. 2.用左右指针在原字符串上扫描，各自跳过无效字符。
  3. 3.统一小写后比较，不同立即 false，相同一起向中间移动。
  4. 4.每个字符最多经过一次，时间 O(n)，额外空间 O(1)。