LeetCode LCR 018. 验证回文串
题目描述
题意分析
判断一个字符串在忽略非字母数字字符、忽略字母大小写后，是否正着读和倒着读相同。数字需要保留，空格与标点等其他字符不参与比较；保留下来的字符仍按原先顺序排列。
题目输入为 ASCII 字符。过滤后没有任何字符，或只剩一个有效字符，都满足回文定义；并不要求原字符串本身没有标点，也不需要真正删除字符后返回新串，只需返回布尔结果。
解法：双指针跳过无效字符
核心思路
[!blue]
回文要求第一个有效字符与最后一个有效字符相同，第二个与倒数第二个相同，依次向中间配对。因此可以直接在原串两端寻找下一对有效字符，不必创建一份过滤后的字符串。
用
left从左向右、right从右向左扫描。每轮先分别跳过非字母数字字符；若两端仍分离，它们指向的就是过滤后序列中尚未比较的首尾字符。将双方按同一种规则转成小写后比较，不等便找到反例，立即返回false。比较通过后同时向内移动。指针外侧的有效字符已经按首尾顺序匹配，指针之间的部分仍待检查；忽略标点只改变寻找有效字符的位置，不改变它们在过滤序列中的先后关系。
跳过无效字符时也要检查
left < right。否则全部剩余字符都是标点时可能越界。若跳过后两指针相遇，剩余范围至多包含一个有效字符，不可能破坏回文；当前实现比较同一位置也必然通过。最终指针相遇或交错，所有需要的字符对都已验证，返回true。
解题步骤
- 左右指针分别指向原串首尾，只在
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]
- 只跳空格、不跳其他符号：题目忽略所有非字母数字字符。
- 把数字也过滤掉：数字属于需要参与对称比较的内容。
- 仅转换一侧大小写：另一侧可能是大写或小写，双方应采用同一种规则。
- 内层跳过时不检查相遇条件：纯标点区间可能让指针越界。
- 比较相同后只移动一端：下一轮不再对应过滤序列的下一对首尾字符，会破坏配对关系。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 680. 验证回文串 II | 简单 | 在双指针回文判断上增加一次删除机会，首次失配需要检查两种跳过方向。 |
| 234. 回文链表 | 简单 | 回文比较条件相同，但单链表不能直接反向访问，需要反转后半段或额外存储。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！