LeetCode LCR 019. 验证回文串 II
题目描述
题意分析
判断整个字符串能否在至多删除一个字符后成为回文。删除是可选的，原串本身已经回文时直接成立；如果需要删除，只能删一个位置，其余字符保持原顺序。
输入只含小写字母，每个字符都参与比较，没有过滤标点或忽略大小写的步骤。单字符天然回文；两字符不等时也可以删除其中一个。任务只要求是否可能，不需要返回删除位置或修改后的字符串。
解法：双指针 + 一次跳过
核心思路
[!blue]
从两端向中间配对，相同的端点可以保留，将问题缩到内部。这里需要保证保留相等端点不会错过某种删除方案：把当前结构写成
x M x，删除发生在M内部时显然仍能保留两端；若某个解删除左端后让M x成为回文，那么非空的M必须以x开头，去掉这一个内部的x后同样留下回文。删右端的情形对称，因此总可以把唯一删除留给内部处理。当第一次出现
s[left] != s[right]时，两端不能同时保留。若删除其他内部位置，这两个不相等的端点仍需互相匹配，矛盾不会消失。因此仅有两种可能：删左端，检查[left + 1, right]；或者删右端，检查[left, right - 1]。不能只根据靠内一位是否相等来选方向，因为开头能够对上不代表后面整段都对称。两种候选分别做一次完整回文判断，任意一种成功即可；第一支成功时可以短路结束，失败才尝试另一支。
此时删除机会已经用完，辅助判断只能逐对比较，不能再次跳过字符。全程只在第一次失配处分两支，不会在每一层递归展开。若主循环一直没有失配，原串本来就是回文，零次删除也合法，直接返回
true。
解题步骤
- 左右指针指向字符串两端，字符相等就同时内缩。
- 第一次失配时，使用普通回文判断检查跳过左端后的区间。
- 如果不成立，再检查跳过右端后的区间，两次结果取逻辑或并直接返回。
- 辅助函数遇到失配立即失败，不允许再次删除。
- 主循环自然结束时，表示无需删除，返回
true。
代码实现
class Solution {
public boolean validPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
// 最多只能删除一个字符，所以只尝试两种跳过方式。
return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
}
}
return true;
}
private boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) {
return false;
}
}
return true;
}
}
func validPalindrome(s string) bool {
left := 0
right := len(s) - 1
for left < right {
if s[left] == s[right] {
left++
right--
} else {
// 删除左字符或右字符，任意一种可行即可。
return isPalindromeRange(s, left+1, right) || isPalindromeRange(s, left, right-1)
}
}
return true
}
func isPalindromeRange(s string, left int, right int) bool {
for left < right {
if s[left] != s[right] {
return false
}
left++
right--
}
return true
}
复杂度分析
- 时间复杂度：
O(n)。主扫描和至多两次区间回文检查都是线性，分支只发生一次。- 空间复杂度：
O(1)。直接用下标检查原串，不构造删除后的副本，辅助判断也采用迭代。
关键点总结
[!green]
- 相等端点可以安全保留，第一次失配才需要使用删除机会。
- 失配端点至少删除一个，所以只检查两个候选方向即可。
- 局部对齐不足以决定方向，两支需要分别验证剩余整段。
- 删除后退化为普通回文判断，不能继续分配新的删除机会。
易错点总结
[!yellow]
- 失配后只尝试删左或只尝试删右：可能漏掉另一方向才成立的解。
- 根据相邻一对字符就固定删除方向：后续区间仍可能失配，不能代替整段检查。
- 同时跳过左右端点：这实际删除了两个字符。
- 辅助函数再次允许删除：会把超过一次删除才能成立的输入误判为真。
- 要求必须删一次：至多一次也包含不删除，原串回文时应直接成立。
- 辅助判断忽略传入区间起点：两支检查的是不同子区间，必须使用各自的左右边界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 125. 验证回文串 | 简单 | 原题只需按过滤规则验证回文，本题在首次失配处增加一次删除选择。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！