LeetCode 125. 验证回文串
目录
题目描述
题意分析
输入一个字符串
s，判断它是不是回文串，返回布尔值。题目对「回文」给出了三条改写规则，缺一不可。其一，只考虑字母和数字，其余字符一律不参与判断，注意是字母和数字两类，不是只有空格，逗号、句号、冒号、井号这些标点同样要被无视。其二，忽略大小写，
A与a视为同一个字符。其三，把符合条件的字符按原顺序取出后，正着读和倒着读必须完全相同。约束信号：字符串长度可达 $2 \times 10^5$，允许包含大小写字母、数字、空格和各类可打印符号，说明必须一遍线性扫描搞定，且不能假设字符集只有小写字母。
边界方面：空字符串定义为回文，返回 true；由此推出，形如
".,"这种删掉非法字符后什么都不剩的串，同样算回文；只剩一个有效字符（如"a."）时必然回文；有效字符个数为奇数时，正中间那个字符不需要和任何人配对。
解法：双指针跳过无效字符
核心思路
问题关键：真正参与判断的只有字母和数字，并且要忽略大小写。先清洗再反转虽然直观，但需要 $O(n)$ 额外空间，也无法在首尾首次失配时提前结束。
为什么选双指针：回文的定义就是第一个有效字符与最后一个有效字符配对、第二个与倒数第二个配对。让
left、right从两端向中间移动，遇到非字母数字就跳过，便能直接在原字符串上完成这些配对。不变量：每轮比较前，区间
[left, right]外侧的有效字符已经成对相等，区间内仍待验证。当前两端跳到有效字符后，若归一化的小写字符不同，可以立即判定不是回文；相同则收缩区间，不变量继续成立。正确性：算法按从外到内的顺序检查每一对有效字符。若中途返回
false，已经找到违反回文定义的一对；若最终left >= right，所有需要配对的字符都相等，剩余至多一个中心字符，因此返回true。
解题步骤
- 初始化
left = 0、right = s.length - 1。- 当
left < right时，分别向内跳过两端所有非字母数字字符；跳过时也要检查left < right，避免指针越界或交叉。- 将两端有效字符统一转成小写后比较，不相等立即返回
false。- 比较成功后执行
left++、right--，继续验证下一对。- 两指针相遇或交叉后返回
true。口述样例：
"A man, a plan, a canal: Panama"从外向内依次比较A/a、m/m、a/a……空格、逗号和冒号都被跳过，所有有效字符配对成功，因此为回文。
代码实现
class Solution {
public boolean isPalindrome(String s) {
int left = 0;
int 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;
}
}
func isPalindrome(s string) bool {
left := 0
right := len(s) - 1
for left < right {
for left < right && !isAlphaNum(s[left]) {
left++
}
for left < right && !isAlphaNum(s[right]) {
right--
}
// 有效字符统一转小写后比较。
if toLower(s[left]) != toLower(s[right]) {
return false
}
left++
right--
}
return true
}
func isAlphaNum(ch byte) bool {
return (ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')
}
func toLower(ch byte) byte {
if ch >= 'A' && ch <= 'Z' {
return ch + 'a' - 'A'
}
return ch
}
复杂度分析
- 时间复杂度：$O(n)$。两个指针都只单向移动，每个字符最多被检查一次。
- 空间复杂度：$O(1)$。只使用两个下标，没有构造清洗后的字符串。
关键点总结
- 回文判断优先想到首尾双指针，既省空间又能提前结束。
- 无效字符无需真正删除，在移动指针时跳过即可。
- 内层移动也必须带
left < right，外层条件不会自动保护内层循环。- 字符归一化必须对两端对称执行；题目字符范围是 ASCII 时，Go 用
byte判断即可。- 进阶到「最多删除一个字符」时，可在首次失配处分叉，分别跳过左端或右端再验证剩余区间。
易错点总结
- 跳过无效字符时漏掉
left < right：纯符号串",.;"会导致越界。- 只跳过空格而不跳过所有非字母数字字符：官方样例会在逗号处误判。
- 只归一化一端：
"Aa"会被错误判为非回文。- 手写有效字符判断时漏掉数字：
"9a0"可能被错误判为回文。- 空串和纯符号串清洗后都是空串，按题意应返回
true，无需额外特判为false。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 680. 验证回文串 II | 简单 | 允许删一个字符，需在首次失配处分叉验证左右两种跳过方案 |
| LCR 018. 验证回文串 | 简单 | 与本题同题，可用来复核跳过非法字符时的 left < right 保护 |
| LCR 019. 验证回文串 II | 简单 | 680 的同题，重点是把失配后的验证抽成可复用的区间回文函数 |