680. 验证回文串 II
题目描述
输入字符串 s。
你可以从 s 中删掉至多一个字符，也可以一个都不删。判断能否由此让 s 变成回文串，即正着读和倒着读相同。能则返回 true，否则返回 false。
示例 1
输入：s = "aba" 输出：true
解释：本身就是回文。
示例 2
输入：s = "abca" 输出：true
解释：删掉 'c'（或 'b'）即可得到回文。
示例 3
输入：s = "abc" 输出：false
解释：删掉任意一个字符都不是回文。
数据范围
1 <= s.length <= 10^5s只包含小写英文字母。
解题思路
双指针 i、j 从两端向中间比较。字符相同就一起往里收，这一步不需要做任何选择。第一次遇到 s[i] ≠ s[j] 时，唯一的删除机会必须用在 s[i] 或 s[j] 上：分别检查删掉左边后的 s[i+1..j]、删掉右边后的 s[i..j-1] 是否为回文，有一个是就返回 true。
为什么正确
外层循环中，s[0..i-1] 与 s[j+1..] 已经对称匹配，且还没有用掉删除机会。
复杂度分析
时间 O(n)，最多扫描约两遍；空间 O(1)。
易错点
失配后两种删法都要试，只试一种会漏掉答案，例如 "cbbcc" 要删右边、"ebcbb…" 类的串可能要删左边。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def validPalindrome(self, s: str) -> bool:
def isPal(i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
i, j = 0, len(s) - 1
while i < j:
if s[i] != s[j]:
return isPal(i + 1, j) or isPal(i, j - 1)
i += 1
j -= 1
return Trueclass Solution {
private String s;
private boolean isPal(int i, int j) {
while (i < j) {
if (s.charAt(i) != s.charAt(j))
return false;
i++;
j--;
}
return true;
}
public boolean validPalindrome(String s) {
this.s = s;
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j))
return isPal(i + 1, j) || isPal(i, j - 1);
i++;
j--;
}
return true;
}
}class Solution {
public:
bool validPalindrome(string s) {
auto isPal = [&](int i, int j) {
while (i < j) {
if (s[i] != s[j])
return false;
i++;
j--;
}
return true;
};
int i = 0, j = (int)s.size() - 1;
while (i < j) {
if (s[i] != s[j])
return isPal(i + 1, j) || isPal(i, j - 1);
i++;
j--;
}
return true;
}
};func validPalindrome(s string) bool {
isPal := func(i, j int) bool {
for i < j {
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
i, j := 0, len(s)-1
for i < j {
if s[i] != s[j] {
return isPal(i+1, j) || isPal(i, j-1)
}
i++
j--
}
return true
}var validPalindrome = function(s) {
const isPal = (i, j) => {
while (i < j) {
if (s[i] !== s[j])
return false;
i++;
j--;
}
return true;
};
let i = 0, j = s.length - 1;
while (i < j) {
if (s[i] !== s[j])
return isPal(i + 1, j) || isPal(i, j - 1);
i++;
j--;
}
return true;
};function validPalindrome(s: string): boolean {
const isPal = (i: number, j: number): boolean => {
while (i < j) {
if (s[i] !== s[j])
return false;
i++;
j--;
}
return true;
};
let i = 0, j = s.length - 1;
while (i < j) {
if (s[i] !== s[j])
return isPal(i + 1, j) || isPal(i, j - 1);
i++;
j--;
}
return true;
}