125. 验证回文串（Valid Palindrome）
频次 ★★★ · 难度 🟢 · 高频：字节/腾讯/美团
题目
给定一个字符串 s，只考虑字母和数字字符，忽略大小写，判断它是否是回文串。
示例：
输入: "A man, a plan, a canal: Panama"
输出: true
输入: "race a car"
输出: false
思路
首尾双指针：左指针从 0 开始，右指针从末尾开始，跳过非字母数字字符，比较 Character.toLowerCase 后的值，如果全部相等则是回文。
代码
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;
if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
return false;
}
left++;
right--;
}
return true;
}复杂度
- 时间：O(n) — 每个字符最多访问一次
- 空间：O(1)
边界条件
- 空串或全非字母数字：跳过所有字符后
left >= right，返回true。 - 单字符：直接返回
true。 - 数字字符：数字参与回文比较，但不需要
toLowerCase（不影响结果）。 - Unicode 字符：
Character.isLetterOrDigit支持大多数 Unicode 字母。
变式
- 只考虑字母忽略数字：把
isLetterOrDigit换成isLetter即可。 - 不忽略大小写：去掉
toLowerCase比较即可。 - 回文链表（234. 回文链表）：值比较 + 快慢指针找中点 + 反转后半段。
- 最多删除一个字符能否构成回文：见 680. Valid Palindrome II，用双指针遇到不相等时尝试跳过左或右。
易错点
- 跳过非字母数字时，内层
while也必须检查left < right，否则可能越界。 - 比较时必须统一
toLowerCase（或toUpperCase），且两边的字符都要转换。 - 不要在跳过前就把字符转小写——非字母数字字符跳过前没有转小写的必要。
面试追问
- 能不能先过滤字符再判断，和双指针比怎样？ 可以，先
filter+toLowerCase得到一个纯净字符串，再双指针或反转比较，但需要 O(n) 额外空间；双指针只用了 O(1) 空间，推荐面试优先给出。 - 如何支持忽略空格和标点但不忽略数字？ 把
isLetterOrDigit改为isLetter即可。