验证回文串 图解题解
一左一右往中间收，谁遇到标点谁自己跳，两边都落到字母才对比——这就是回文判断的全部逻辑。
两个探针各从字符串两端往中间移。左探针碰到标点，只移左探针往右走一格，右探针不动；右探针碰到标点，只移右探针往左走一格，左探针不动。两边都落到字母数字上才比一对，比完再各自向内走。某一侧独自跳过杂质、另一侧原地等——不是两侧同步推进，这是这道题最容易搞错的地方。
这道题到底在问什么
- 输入
- s = "Abc, dEf:ed cba"
- 输出
- true（清洗后是 abcdefedcba，正反读一样）
最优解：一步一步想明白
- 3记住两个动作：清洗（留字母数字、转小写），双指针从两头夹向中间一对对比。下面每一帧都在套它。
- 4先把原串清洗：逗号、冒号、空格都删掉，大写 A、E 变成小写 a、e。得到上面这 13 个干净字符，接下来就在它上面比对。
- 5左指针 l 落在最左边的下标 0，右指针 r 落在最右边的下标 12。两人准备从两头往中间一对对地比。
- 6第一对里，左指针 l 在下标 0，它的字符是 'a'（高亮这位）。
- 7右指针 r 在下标 12，它的字符是 'a'。现在把这一对的两个字符 'a' 和 'a' 拿来比。
- 8'a' 和 'a' 相等，这一对通过。左指针往右挪一格、右指针往左挪一格，去比更靠中间的下一对。
- 9第二对里，左指针 l 在下标 1，它的字符是 'b'（高亮这位）。
- 10右指针 r 在下标 11，它的字符是 'b'。现在把这一对的两个字符 'b' 和 'b' 拿来比。
- 11'b' 和 'b' 相等，这一对通过。左指针往右挪一格、右指针往左挪一格，去比更靠中间的下一对。
- 12第三对里，左指针 l 在下标 2，它的字符是 'c'（高亮这位）。
- 13右指针 r 在下标 10，它的字符是 'c'。现在把这一对的两个字符 'c' 和 'c' 拿来比。
- 14'c' 和 'c' 相等，这一对通过。左指针往右挪一格、右指针往左挪一格，去比更靠中间的下一对。
- 15第四对里，左指针 l 在下标 3，它的字符是 'd'（高亮这位）。
- 16右指针 r 在下标 9，它的字符是 'd'。现在把这一对的两个字符 'd' 和 'd' 拿来比。
- 17'd' 和 'd' 相等，这一对通过。左指针往右挪一格、右指针往左挪一格，去比更靠中间的下一对。
- 18第五对里，左指针 l 在下标 4，它的字符是 'e'（高亮这位）。
- 19右指针 r 在下标 8，它的字符是 'e'。现在把这一对的两个字符 'e' 和 'e' 拿来比。
- 20'e' 和 'e' 相等，这一对通过。左指针往右挪一格、右指针往左挪一格，去比更靠中间的下一对。
- 21第六对里，左指针 l 在下标 5，它的字符是 'f'（高亮这位）。
- 22右指针 r 在下标 7，它的字符是 'f'。现在把这一对的两个字符 'f' 和 'f' 拿来比。
- 23'f' 和 'f' 相等，这一对通过。左指针往右挪一格、右指针往左挪一格，去比更靠中间的下一对。
- 24左右指针在中间相遇（下标 6 这一格无需再比）。一路上每一对字符都相等，所以它是回文，返回 true。
⚠️ 容易写错的地方
✗ 错：忘了忽略大小写，把 'A' 和 'a' 当成不同
✓ 对：清洗时统一转小写再比
题目要求大小写不敏感，不转小写会把本来相等的一对判成不等
✗ 错：没过滤标点空格，直接在原串上比
✓ 对：先只保留字母和数字
逗号、空格会占位置，让左右指针错位、比错对象
✗ 错：指针越界或漏掉相遇判断
✓ 对：循环条件用 while l < r
l 与 r 相遇（指向中间那格）时无需再比，继续比会重复甚至越界
完整代码（Python / C++ / Java）
Python
def isPalindrome(s):
t = [c.lower() for c in s if c.isalnum()] # 清洗:留字母数字+转小写
l, r = 0, len(t) - 1
while l < r:
if t[l] != t[r]: # 有一对不相等
return False
l += 1 # 两指针一起往中间挪
r -= 1
return TrueC++
bool isPalindrome(string s) {
string t;
for (char c : s) if (isalnum(c)) t += tolower(c);
int l = 0, r = t.size() - 1;
while (l < r) {
if (t[l] != t[r]) return false;
l++; r--;
}
return true;
}Java
public boolean isPalindrome(String s) {
StringBuilder b = new StringBuilder();
for (char c : s.toCharArray())
if (Character.isLetterOrDigit(c)) b.append(Character.toLowerCase(c));
int l = 0, r = b.length() - 1;
while (l < r) {
if (b.charAt(l) != b.charAt(r)) return false;
l++; r--;
}
return true;
}复杂度
时间
O(n)
清洗扫一遍、双指针再扫一遍，都是线性，n 是字符串长度
空间
O(n)
清洗后的字符序列要额外存一份；若原地跳过非字母数字可优化到 O(1)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 验证回文串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么要先清洗再判断？+
题目只看字母和数字、且大小写不敏感。不先清洗，标点空格会占位、大小写会误判，导致左右指针比错对象。
空字符串或清洗后为空，算回文吗？+
算，返回 true。l 从 0 开始、r 是 -1，while l < r 一次都不进，直接返回 true。
能不能不额外建清洗后的串，省到 O(1) 空间？+
能。直接在原串上用 l/r 两指针，遇到非字母数字就跳过（l++ 或 r--），比较时临时转小写，这样不用额外数组。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 验证回文串 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。