题目:给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
示例 1：
// 输入: s = "aba"
// 输出: true
示例 2：
// 输入: s = "abca"
// 输出: true
// 解释: 可以删除 "c" 字符 或者 "b" 字符
示例 3：
// 输入: s = "abc"
// 输出: false
提示:
- 1 <= s.length <= 2 * 10 ^ 5
- s 由小写英文字母组成
注意：本题与LeetCode 680 题相同。
思路分析
本题思路和有效的回文很相似，我们可以定义2个指针left和right，然后判断两边字符（s[left] === s[right]）是否相等，如果不相等，再比较是去除左边一个字符即left指针加1是否和右边字符相等（s[left + 1] === s[right]）或者去除右边一个字符，即right指针减1（s[left] === s[right - 1]）。代码如下:
var isPalindrome = function(s,start,end){
while(start < end){
if(s[start] !== s[end]){
return false;
}
start++;
end--;
}
return true;
}
/**
* @param {string} s
* @return {boolean}
*/
var validPalindrome = function(s) {
let len = s.length,left = 0,right = len - 1;
while(left < right){
if(s[left] !== s[right]){
return isPalindrome(s,left + 1,right) || isPalindrome(s,left,right - 1);
}
left++;
right--;
}
return true;
};
以上算法的时间复杂度和空间复杂度分析如下:
- 时间复杂度：O(n * m)。
- 空间复杂度：O(1)。
Comments