LeetCode 125. 验证回文串
题目描述
题意分析
只保留字符串中的英文字母和数字，忽略字母大小写后，判断剩余序列从前往后与从后往前是否一致。空格、标点等其他字符不参与比较，数字则必须保留。
删除无效字符只是题目对比较规则的描述，不要求实际修改字符串。没有有效字符时，剩余序列为空，按回文处理；奇数个有效字符时，中间一个字符不影响判断。
解法：双指针跳过无效字符
核心思路
[!blue]
回文要求最左、最右的有效字符相同，去掉这对字符后，剩余部分仍然需要满足同样条件。因此可以用左右指针从两端向中间靠拢，逐对验证，不需要额外构造清洗后的字符串。
每一轮先让左指针跳过非字母数字字符，右指针也做同样处理。此时两端剩下的就是尚未验证序列中最外面的一对有效字符；把两者都转为小写后比较，不相等即可确定整串不是回文，相等则同时向内移动一格。
循环始终保持：两个指针外侧的有效字符已经一一配对成功，而区间内仍是待验证部分。跳过的字符按题意本来就不参与比较，不会丢掉需要检查的内容；相等的一对删除后也不会改变内部回文条件。
跳过字符的内层循环同样要检查
left < right，否则纯标点输入可能一直走出边界。指针相遇时至多剩一个字符，不需要再与别处配对；代码比较同一位置也会自然通过，随后结束循环。
解题步骤
- 初始化
left = 0、right = s.length - 1。- 当
left < right时，先从左边跳过非字母数字字符，再从右边跳过，两个内部循环都保留边界判断。- 将两端字符都转为小写。若不同，立即返回
false。- 若相同，令左指针右移、右指针左移，继续检查下一对。
- 两指针相遇或交叉后，说明所有需要配对的字符都匹配，返回
true。
代码实现
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)$。只使用两个下标，没有构造清洗后的字符串。
关键点总结
[!green]
- 跳过无效字符相当于即时过滤，保留双指针的常数空间优势。
- 字符范围与大小写归一化是两件事：先确认哪些参与比较，再统一字母大小写。
- 已配对区间不断扩大，未处理区间不断缩小，每个字符最多被经过一次。
易错点总结
[!yellow]
- 内层跳过字符时不检查边界，外层开始时的条件无法防止连续跳过之后越界。
- 只忽略空格，会错误地把其他标点当作有效字符参与比较。
- 只判断字母而漏掉数字，会删除本应保留的比较内容。
- 只对其中一端转小写，无法正确忽略大小写差异。
- 把没有有效字符的输入判为
false，不符合空序列也是回文的定义。- 本题输入为可打印 ASCII 字符，因此 Go 按字节扫描与这里的有效字符规则一致。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 680. 验证回文串 II | 简单 | 在双指针回文判断上增加一次删除机会，首次失配需要检查两种跳过方向。 |
| 234. 回文链表 | 简单 | 回文比较条件相同，但单链表不能直接反向访问，需要反转后半段或额外存储。 |
| 补充题 137. 区分大小写与标点的回文判定 | 中等 | 都用左右指针从两端逐对比较；本题跳过标点并忽略大小写，补充题按原字符比较。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！