Python算法训练序列

双指针与滑动窗口 · Unit 01

← Unit 00

125

LeetCode 125Valid Palindrome · 验证回文串

先决定“比较谁”，
再决定左右指针怎样移动。

回文判断不是简单地比较字符串首尾。本题要求忽略标点和空格，并且不区分大小写。因此，左右指针首先要跳过无效字符，然后才比较当前有效字符。

LeetCode #125 原题内容 中文转述 · 示例、约束与提交签名

题目要求

如果一个字符串在转换为小写并移除所有非字母数字字符后，正着读和反着读完全相同，则称它为回文串。给定字符串 s，判断它是否为回文串。

class Solution: def isPalindrome(self, s: str) -> bool: # 在这里提交答案

约束

1 ≤ len(s) ≤ 200000
s 由可打印 ASCII 字符组成。

示例

s = "A man, a plan, a canal: Panama"
输出：True
规范化后："amanaplanacanalpanama"

s = "race a car"
输出：False
规范化后："raceacar"

s = " "
输出：True
移除非字母数字字符后为空串。

1. 确定有效字符

2. 执行左右比较

3. 建立不变量

4. 代码联动

5. 删除一次迁移

演示字符串"A,ba"

规范化视图：只保留字母数字并转小写

aba

当前循环不变量

left 左侧与 right 右侧的有效字符已经成对匹配。

当前移动规则

无效字符只移动其所在一侧；有效字符比较后同时向中间移动。

left0

right3

当前字符A / a

比较结果等待

函数状态运行中

补全 LeetCode 提交代码卡住可查看参考答案

class Solution:

def isPalindrome(self, s: str) -> bool:

left, right =

while left < right:

while left < right and :

left += 1

while left < right and :

right -= 1

if :

return False

left += 1

right -= 1

return True

class Solution: def isPalindrome(self, s: str) -> bool: left, right = 0, len(s) - 1 while left < right: while left < right and not s[left].isalnum(): left += 1 while left < right and not s[right].isalnum(): right -= 1 if s[left].lower() != s[right].lower(): return False left += 1 right -= 1 return True

也可以先构造规范化字符串再反转比较：cleaned == cleaned[::-1]。这种写法简洁，但需要额外 O(n) 空间；双指针版本直接在原字符串上跳过无效字符，额外空间为 O(1)，也更适合训练移动依据。

代码—字符—指针联动轨迹示例：s="A,b_a"

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1
            if s[left].lower() != s[right].lower():
                return False
            left += 1
            right -= 1
        return True

点击下一行，观察左右指针如何跳过逗号和下划线。

完成代码联动后进入迁移练习 补全正确、查看答案或播放完整轨迹后解锁。

迁移题：允许删除至多一个字符

给定只含小写字母的字符串，允许删除至多一个字符，判断能否变成回文串。例如 "abca" 删除 b 或 c 后可以成为回文串。这对应 LeetCode #680 的核心思路。

本单元形成的算法Skill

面对忽略部分字符的镜像比较问题，先定义“有效字符”，再让左右指针分别跳过无效位置。每次比较相等后同时向中间移动；一旦有效字符不等即可立即失败。

LeetCode #125 相向双指针字符过滤大小写统一时间 O(n) 额外空间 O(1)

Unit 00 已完成双指针前置心智模型

#125 当前：回文比较相向指针＋过滤

#283 下一单元移动零：同向读写指针

#167 后续单元有序数组单调排除