题目描述
思路解析动画文字版
我们只需要在第一次左右字符不等时分叉一次，因为前面已经匹配过，后面也只剩两个可能的删除位置。
helper check 是严格回文检查：进入 check 之后不能再删第二个字符。
初始化：l=0，r=3：主流程先用左右指针检查完整字符串 abca。
比较两端：a 和 a 相等：两端相等，说明这两个字符不用删除，可以放心往中间收缩。
指针内收：l=1，r=2：外层已经确认的 a/a 不会再影响答案，真正的问题落在中间的 b/c。
第一次不匹配：b 和 c：这是第一次不匹配。因为最多只能删一个字符，所以现在只剩两条路：跳过 b，或者跳过 c。
候选一：跳过左边 b：外层原始指针记录为 outerL=1、outerR=2；候选一把 helper 的检查区间改成 checkL=2、checkR=2，相当于跳过左字符 b。单个字符天然是回文。
候选一结果：check(2,2) 为 true：注意 check 里没有再次删除的机会；此时 l==r，while l < r 不进入，直接返回 True。
候选二：跳过右边 c：外层原始指针记录为 outerL=1、outerR=2；候选二把 helper 的检查区间改成 checkL=1、checkR=1，相当于跳过右字符 c。
候选二结果：check(1,1) 为 true：abca 这一例里，删 b 或删 c 都能成功。此时 l==r，check 直接返回 True；代码用 or，任意一个候选为 true 就能返回 true。
收束：两个候选做 or：第一次不匹配时已经用掉删除机会，返回两个严格回文检查结果的 or。
反例：abc 为什么是 false：如果两个候选区间都不是普通回文，就说明删一个字符也救不了。
这也是双指针题里常见的贪心边界：前面相等的字符没必要回头改。
参考代码
class Solution: def validPalindrome(self, s): def check(l, r): while l < r: if s[l] != s[r]: return False l += 1 r -= 1 return True l = 0 r = len(s) - 1 while l < r: if s[l] != s[r]: return check(l + 1, r) or check(l, r - 1) l += 1 r -= 1 return True复杂度
- 时间复杂度：O(n)，外层最多扫一遍；第一次不匹配时最多再检查两个不重叠候选区间的线性长度。
- 空间复杂度：O(1)，只使用左右指针，没有构造新字符串。
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最接近的三数之和
LeetCode 16 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题