最多删除一个字符得到回文
# 📃 题目描述
题目链接:
- 剑指 Offer II 019. 最多删除一个字符得到回文 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
- 680. 验证回文字符串 Ⅱ - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个非空字符串 s,请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
示例 1:
输入: s = "aba"
输出: true
示例 2:
输入: s = "abca"
输出: true
解释: 可以删除 "c" 字符 或者 "b" 字符
# 🔔 解题思路
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 指向的字符之后再判断能否形成回文
return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1);
}
left ++;
right --;
}
// 能够正常走出 while 循环,说明 s 本身就是一个回文串
return true;
}
// 左闭右闭
private boolean isPalindrome(String s, int left, int right) {
if (left == right) {
return true;
}
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left ++;
right --;
}
return true;
}
}
# 💥 复杂度分析
- 空间复杂度:O(1)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10