LeetCode 125简单双指针
验证回文串 图解题解
一左一右往中间收，谁遇到标点谁自己跳，两边都落到字母才对比——这就是回文判断的全部逻辑。
两个探针各从字符串两端往中间移。左探针碰到标点，只移左探针往右走一格，右探针不动；右探针碰到标点，只移右探针往左走一格，左探针不动。两边都落到字母数字上才比一对，比完再各自向内走。某一侧独自跳过杂质、另一侧原地等——不是两侧同步推进，这是这道题最容易搞错的地方。
这道题到底在问什么
只考虑字母和数字、忽略大小写，判断字符串是否为回文。
- s
- "A?bCb?a"
- 清洗后
- "abcba"
- 输出
- true
最优解：一步一步想明白
- 3最直接的想法：先 for 一遍过滤掉标点、转小写造出 "abcba"，再反转比较。能做，但白白多扫一遍、多开一个字符串。
- 4转折：不必造新串。l 从左、r 从右同时向里走，谁指向标点就只移谁、不比较（这就是负例动作）；两边都落在字母数字上时才转小写比一对。相遇即说明全程对称。O(1) 额外空间。
- 5l=0, r=6左指针 l=0 指 A，右指针 r=6 指 a。开始向中间收。
- 6'A' vs 'a'两端都是字母，转小写：'A'→'a'、'a'→'a'。比一下。
- 7'a' == 'a' ✓'a' == 'a'，这一对通过，l 右移、r 左移。
- 8l 右移，不比较l 指向 '?'，不是字母数字。不比较，只让 l 前进到 2——r 原地不动。这就是「跳过杂质」的负例动作。
- 9r 左移，不比较r 也指向 '?'，同样只退 r 到 4、不比较。现在 l=2、r=4 都落在字母上了。
- 10'b' vs 'b'l=2 是 'b'、r=4 是 'b'，两边都落在字母上，可以比了。
- 11'b' == 'b' ✓'b' == 'b'，通过！内收：l→3、r→3。
- 12l ≥ r，全程无不等l、r 在中间的 C 相遇（中点字符自己和自己对称，无需比）。全程每一对都相等，返回 true。
- 15回文类问题的通用套路：左右指针向中间走、逐对比较；遇到要忽略的字符就只移动那侧的指针。
⚠️ 容易写错的地方
✗ 错：内层跳过时不判 l < r
✓ 对：while 里始终带 l < r
全是杂质时指针会越界
✗ 错：比较忘了统一大小写
✓ 对：都 .lower() 再比
题目忽略大小写
完整代码（Python / C++ / Java）
Python
class Solution:
def isPalindrome(self, s):
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum(): l += 1 # 跳过非字母数字
while l < r and not s[r].isalnum(): r -= 1
if s[l].lower() != s[r].lower(): # 忽略大小写
return False
l += 1; r -= 1
return TrueC++
class Solution {
public:
bool isPalindrome(string s) {
int l = 0, r = s.size() - 1;
while (l < r) {
while (l < r && !isalnum(s[l])) l++; // 跳过非字母数字
while (l < r && !isalnum(s[r])) r--;
if (tolower(s[l]) != tolower(s[r])) return false;
l++; r--;
}
return true;
}
};Java
class Solution {
public boolean isPalindrome(String s) {
int l = 0, r = s.length() - 1;
while (l < r) {
while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
return false;
l++; r--;
}
return true;
}
}套路模板 · 双指针回文（背下来）
l, r = 0, n - 1
while l < r:
while l < r and 该跳过(s[l]): l += 1
while l < r and 该跳过(s[r]): r -= 1
if 规范化(s[l]) != 规范化(s[r]): return False
l += 1; r -= 1
return True复杂度
时间复杂度
O(n)
每个字符最多看一次
空间复杂度
O(1)
原地双指针
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 验证回文串 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
对撞双指针：l 从头、r 从尾；各自跳过非字母数字字符，再忽略大小写比较；不等即 false、相遇即 true。O(n)、O(1) 空间。
先清洗成新串再判可以吗？+
可以：过滤+转小写生成新串再首尾比，但要 O(n) 额外空间；双指针原地跳过不开新串，O(1) 空间更优。
判字母数字/转小写要注意什么？+
用内置 isalnum / isLetterOrDigit 判字母数字、tolower / toLowerCase 转小写；注意只对 ASCII 可靠，Unicode 需额外处理。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。