剑指OfferII019.最多删除一个字符得到回文

---

comments: true edit_url: github /doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20019.%20%E6%9C%80%E5%A4%9A%E5%88%A0%E9%99%A4%E4%B8%80%E4%B8%AA%E5%AD%97%E7%AC%A6%E5%BE%97%E5%88%B0%E5%9B%9E%E6%96%87/README.md 剑指 Offer II 019. 最多删除一个字符得到回文 题目描述

给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

 

示例 1:

输入: s = "aba" 输出: true

示例 2:

输入: s = "abca" 输出: true 解释: 可以删除 "c" 字符 或者 "b" 字符

示例 3:

输入: s = "abc" 输出: false

 

提示:

1 <= s.length <= 105s 由小写英文字母组成

 

注意：本题与主站 680 题相同：  leetcode /problems/valid-palindrome-ii/

解法 方法一：双指针

我们用两个指针 i i i 和 j j j 分别指向字符串 s s s 的第一个字符和最后一个字符，然后向中间移动指针，每次判断 s [ i ] s[i] s[i] 和 s [ j ] s[j] s[j] 是否相等：

如果 s [ i ] = s [ j ] s[i] = s[j] s[i]=s[j]，则指针 i i i 向后移动一位，指针 j j j 向前移动一位；否则，存在两种情况，即删除字符 s [ i ] s[i] s[i] 或者删除字符 s [ j ] s[j] s[j]，然后判断删除之后的字符串是否是回文字符串。即判断子串 s [ i + 1.. j ] s[i+1..j] s[i+1..j] 或者子串 s [ i . . j − 1 ] s[i..j-1] s[i..j−1] 是否是回文字符串。【若存在回文，s[i],s[j]中必有一个阻塞】

时间复杂度 O ( n ) O(n) O(n)，其中 n n n 是字符串 s s s 的长度。空间复杂度 O ( 1 ) O(1) O(1)。

Python3 class Solution: def validPalindrome(self, s: str) -> bool: def check(i,j): while i<j: if s[i]!=s[j]:return False i,j=i+1,j-1 return True l,r=0,len(s)-1 while l<r: if s[l]!=s[r]: #若存在回文，s[i],s[j]中必有一个阻塞 return check(l,r-1) or check(l+1,r) l,r=l+1,r-1 return True #本身就是回文,while中就不会经过if Java class Solution { private String s; public boolean validPalindrome(String s) { this.s = s; for (int i = 0, j = s.length() - 1; i < j; ++i, --j) { if (s.charAt(i) != s.charAt(j)) { return check(i + 1, j) || check(i, j - 1); } } return true; } private boolean check(int i, int j) { for (; i < j; ++i, --j) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; } } C++ class Solution { public: bool validPalindrome(string s) { auto check = [&](int i, int j) { for (; i < j; ++i, --j) { if (s[i] != s[j]) { return false; } } return true; }; for (int i = 0, j = s.size() - 1; i < j; ++i, --j) { if (s[i] != s[j]) { return check(i + 1, j) || check(i, j - 1); } } return true; } }; Go func validPalindrome(s string) bool { check := func(i, j int) bool { for ; i < j; i, j = i+1, j-1 { if s[i] != s[j] { return false } } return true } for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { if s[i] != s[j] { return check(i+1, j) || check(i, j-1) } } return true } TypeScript function validPalindrome(s: string): boolean { const check = (i: number, j: number): boolean => { for (; i < j; ++i, --j) { if (s[i] !== s[j]) { return false; } } return true; }; for (let i = 0, j = s.length - 1; i < j; ++i, --j) { if (s[i] !== s[j]) { return check(i + 1, j) || check(i, j - 1); } } return true; } JavaScript /** * @param {string} s * @return {boolean} */ var validPalindrome = function (s) { const check = (i, j) => { for (; i < j; ++i, --j) { if (s[i] !== s[j]) { return false; } } return true; }; for (let i = 0, j = s.length - 1; i < j; ++i, --j) { if (s[i] !== s[j]) { return check(i + 1, j) || check(i, j - 1); } } return true; }; Swift class Solution { private var s: String = "" func validPalindrome(_ s: String) -> Bool { self.s = s var i = s.startIndex var j = s.index(before: s.endIndex) while i < j { if s[i] != s[j] { return check(s.index(after: i), j) || check(i, s.index(before: j)) } i = s.index(after: i) j = s.index(before: j) } return true } private func check(_ i: String.Index, _ j: String.Index) -> Bool { var i = i var j = j while i < j { if s[i] != s[j] { return false } i = s.index(after: i) j = s.index(before: j) } return true } }