LeetCode LCR 018. 验证回文串
目录
题目描述
题意分析
输入一个字符串
s，判断它是不是回文串，返回布尔值。题目对「回文」给出了三条改写规则，缺一不可。其一，只考虑字母和数字，其余字符一律不参与判断，注意是字母和数字两类，不是只有空格，逗号、句号、冒号、井号这些标点同样要被无视。其二，忽略大小写，
A与a视为同一个字符。其三，把符合条件的字符按原顺序取出后，正着读和倒着读必须完全相同。约束信号：字符串长度可达 $2 \times 10^5$，允许包含大小写字母、数字、空格和各类可打印符号，说明必须一遍线性扫描搞定，且不能假设字符集只有小写字母。
边界方面：空字符串定义为回文，返回 true；由此推出，形如
".,"这种删掉非法字符后什么都不剩的串，同样算回文；只剩一个有效字符（如"a."）时必然回文；有效字符个数为奇数时，正中间那个字符不需要和任何人配对。
解法：双指针跳过无效字符
核心思路
最朴素的做法完全照着题面翻译：先遍历一遍原串，把字母和数字挑出来、统一转成小写，拼成一个干净的新串，再把新串整体反转，比较两者是否相等。逻辑上无懈可击，但代价是额外开了两份长度为 $O(n)$ 的字符串；而且它必须先把整个串处理完才开始比较，哪怕第一个字符和最后一个字符就已经对不上，也白白做完了全部工作。瓶颈就在这两处：多余的空间，以及无法提前退出。
观察点在于：判断回文本质上是一系列「首尾配对」的比较，第 i 个有效字符要和倒数第 i 个有效字符相等。既然是从两端向中间成对推进，就没必要真的构造出那个干净字符串——只要能在原串上分别找到「从左数第 i 个有效字符」和「从右数第 i 个有效字符」的位置即可。这正是双指针的用武之地：
left从 0 出发向右，right从末尾出发向左，各自负责跳过途中所有非字母数字字符，跳到停下来时，两人指向的就是当前待配对的一对有效字符。由此得到需要全程维持的不变量：每轮比较开始前，
s[0..left)中的有效字符已经与s(right..n-1]中的有效字符按首尾顺序两两匹配成功，且区间[left, right]内尚未有任何一对被检验过。也就是说，外侧是已经确认对称的部分，内侧是待定的部分，两个指针就是这条分界线。每完成一次成功比较，就执行left++与right--，把这对字符从待定区移入已确认区，区间严格收缩；一旦某次比较失败，说明存在一对无法匹配的首尾字符，可以立刻返回 false，天然具备提前退出的能力。收缩终止于
left >= right：此时待定区要么为空（有效字符个数为偶数），要么只剩正中间一个字符（个数为奇数），而单个字符自己与自己对称，无需比较。既然待定区不可能再破坏对称性，直接返回 true。比较时对两端字符各做一次转小写，就顺带满足了「忽略大小写」这条规则。注意跳过非法字符的内层循环必须自己也带上left < right的条件，否则当剩余字符全是标点时指针会越过对方，读到越界或错误的位置。
解题步骤
left置 0，right置s.length() - 1，外层循环条件为left < right。为什么用严格小于：两指针相遇（指向同一个字符）时待定区只剩中心一个字符，它天然自对称，再比较一次纯属多余。- 内层第一个循环把
left向右推进，直到指向字母或数字，推进条件里同时写上left < right。为什么必须带这个条件：像",,,"这类全是标点的输入，若不加限制left会一路冲过right直至越界；带上后指针最多停在right上，外层随即结束并返回 true，正好符合「无有效字符视为回文」。- 内层第二个循环同理把
right向左推进，条件同样带left < right。为什么右指针也要判：左指针跳完后位置可能已经变了，右指针必须以最新的left为下界，否则在"a,,,"这类输入上会反向越过左指针。- 把
s[left]与s[right]各转成小写后比较，不等立即返回 false。为什么两边都要转：只转一边等于假设另一边必是小写，遇到"Aa"就会误判；转小写还是转大写不重要，关键是两侧做同一种归一化。- 比较通过后执行
left++、right--，回到外层循环继续。为什么必须同时移动：这一步是把刚确认的一对字符移出待定区、兑现不变量的动作，只动一侧会让指针原地反复比较同一对字符而死循环。- 循环自然结束时返回 true。为什么可以直接返回：能走到这里意味着每一对首尾有效字符都比较成功过，没有任何反例，符合回文定义。
- 以
"A man, a plan, a canal: Panama"走一遍：初始left = 0（A）、right = 29（a），两者都是有效字符，转小写后同为a，比较通过，收缩为left = 1、right = 28。此时left指向空格，内层循环推进到下标 2 的m，right指向的m无需移动，比较通过。接着a对a、n对n连续通过，left走到下标 5 的逗号，连跳逗号与空格两格来到下标 7 的a，与right = 25的a匹配。随后left跳过空格来到下标 9 的p，与right = 24的大写P比较，正是靠统一转小写才判等；这一步也说明只跳空格不跳标点的写法会在前面的逗号处就翻车。再往后left = 10的l对应右侧，right需要先跳过下标 23 的空格、再跳过下标 22 的冒号，才落到下标 21 的l，比较通过。中段a、n依次配对后，left从下标 13 的逗号连跳到下标 15 的a，与right = 18的a匹配，收缩为left = 16、right = 17。最后一轮left指向空格，内层循环因left < right的保护只推进到 17 便停下，两指针指向同一个c，比较自然通过，收缩后left = 18 > right = 16，外层结束，返回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)$。凭什么是线性：虽然写了三层循环，但
left只增不减、right只减不增，两者合计移动的总步数不超过 n，每个下标至多被访问一次；判断字母数字与转小写都是 $O(1)$ 的常数操作。嵌套循环的层数与复杂度无关，真正的度量是指针的总位移。- 空间复杂度：$O(1)$。凭什么：全程在原字符串上就地扫描，只额外保存两个整型下标，没有构造过滤后的新串，也没有递归栈开销。这正是相比「先清洗再反转比较」写法的核心优势。
关键点总结
- 判断回文的通用范式是首尾双指针向中心收缩，比「反转后整体比较」省下一份 $O(n)$ 空间，还能在第一处不匹配时立即返回。
- 「忽略某类字符」不必真的删除它们，在扫描时跳过即可。这个「视图式过滤」的思路可以迁移到任何「只关心子集元素相对顺序」的题目，避免构造中间数组。
- 收缩型双指针一定要写清楚不变量：外侧已确认、内侧待定。所有指针移动都应是在兑现这条不变量，想不清楚移动理由时，多半就是漏了某个边界判断。
- 内层跳过循环必须重复外层的
left < right条件。嵌套循环里的每个指针推进都可能越界，边界条件不会自动继承，这是双指针类题目最高频的踩坑点。- 面试视角：本题常被追问「如果不允许修改原串、也不允许额外空间还能怎么写」「大小写归一化能否只用位运算」，以及进阶的 680 题「允许删除一个字符时怎么办」——后者的答案是在第一次失配处分叉，分别尝试跳过左侧或右侧字符再验证剩余区间。
- 归一化要对称地作用于比较双方。只对一侧做转换是逻辑漏洞，而不是性能优化。
易错点总结
- 错误写法：内层跳过循环只写
while (!isLetterOrDigit(s.charAt(left)))，省掉left < right。用例",.;"→left一路向右冲出字符串末尾，charAt抛出下标越界异常；即便侥幸不越界，也会与right交叉后比较到错误的字符对。- 错误写法：只跳过空格，写成
while (s.charAt(left) == ' ')。用例"A man, a plan, a canal: Panama"→ 走到下标 5 的逗号时不会跳过，拿逗号去和右侧的a比较直接返回 false，正确答案却是 true。题目要求的是「只保留字母和数字」，标点、下划线、井号统统要跳。- 错误写法：比较时只对一侧调用
toLowerCase。用例"Aa"→A与小写后的a不等，返回 false，实际应为 true。两端必须做同一种归一化。- 错误写法：用
s.charAt(left) >= 'a' && s.charAt(left) <= 'z'之类的手写判断，却漏掉数字分支。用例"1a2b2a1"→ 数字被当成无效字符跳过，虽然本例答案仍为 true，但在"0a0"与"9a0"上会给出相同结果，后者本应为 false。数字是有效字符。- 错误写法：在 ASCII 判断中直接用
ch - 'a' >= 0一类的表达式覆盖大小写。用例"P0"→ 大写字母的 ASCII 码小于a，被误判为无效字符跳过，字符串被视为只剩0，错误返回 true，正确答案是 false（p与0不等）。- 错误写法：比较通过后只写
left++而忘记right--。用例"aba"→left不断右移，right停在末尾，b与a比较后返回 false；某些写法下还会在同一对字符上原地打转造成死循环。- 错误写法：内层用
left < s.length()、right >= 0作为越界保护，跳完后不再判断left < right就直接比较。用例",."→left停在 2、right停在 -1，随后的charAt立刻抛异常；即使换成先比较再判断，也会拿交叉后的错位字符得出无意义的结论。跳过循环之后指针关系可能已经反转，比较前必须重新确认。- 错误写法：认为空串或纯符号串无法构成回文而特判返回 false。用例
""与".,"→ 题目明确规定空字符串视为有效回文，正确答案都是 true，双指针写法在left < right一开始就不成立时自然返回 true，本就不需要任何特判。- 错误写法：为图省事先
s = s.replaceAll("[^a-zA-Z0-9]", "").toLowerCase()再反转比较。用例"A man, a plan, a canal: Panama"→ 结果正确，但对长度 $2 \times 10^5$ 的输入会额外占用 $O(n)$ 空间，且丧失了提前退出的能力，面试中被追问空间优化时会失分。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 680. 验证回文串 II | 简单 | 允许删一个字符，需在首次失配处分叉验证左右两种跳过方案 |
| LCR 019. 验证回文串 II | 简单 | 680 的同题，重点是把失配后的验证抽成可复用的区间回文函数 |