题目样例
示例 1
输入
"aba"
输出
True
解释
本身就是回文
示例 2
输入
"abca"
输出
True
解释
可以删除 b 或者 c 字符
题目思考
解决方案
方案 1
思路
复杂度
代码
Python 3
class Solution:
def validPalindrome(self, s: str) -> bool:
def check(b, e, canDelete):
if b >= e:
return True
if s[b] == s[e]:
return check(b + 1, e - 1, canDelete)
elif canDelete:
# 还有一次删除机会, 左指针右移或者右指针左移, 同时更新flag保证之后的判断不能再删除字符了
return check(b + 1, e, False) or check(b, e - 1, False)
else:
# 遇到不相等的字符且不能再删除了, 直接返回false
return False
return check(0, len(s) - 1, True)
C++
class Solution {
public:
bool validPalindrome(string s) {
function<bool(int, int, bool)> check = [&](int b, int e, bool canDelete) {
while (b < e && s[b] == s[e]) {
++b;
--e;
}
if (b >= e) {
return true;
}
if (!canDelete) {
return false;
}
return check(b + 1, e, false) || check(b, e - 1, false);
};
return check(0, s.size() - 1, true);
}
};
方案 2
思路
复杂度
代码
Python 3
class Solution:
def validPalindrome(self, s: str) -> bool:
b = 0
e = len(s) - 1
def isPalindrome(b, e):
while b < e:
if s[b] == s[e]:
b += 1
e -= 1
else:
return False
return True
while b < e:
if s[b] == s[e]:
b += 1
e -= 1
else:
return isPalindrome(b + 1, e) or isPalindrome(b, e - 1)
return True
C++
class Solution {
public:
bool validPalindrome(string s) {
auto isPalindrome = [&](int b, int e) {
for(; b < e; ++b, --e) {
if (s[b] != s[e]) {
return false;
}
}
return true;
};
int b = 0;
int e = s.size() - 1;
while (b < e && s[b] == s[e]) {
++b;
--e;
}
if (b >= e) {
return true;
}
return isPalindrome(b + 1, e) || isPalindrome(b, e - 1);
}
};
方案 3
思路
复杂度
参考资料
本文分享自微信公众号 - 每日精选算法题（DailyAlgorithm）。
如有侵权，请联系 [email protected] 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。