680 验证回文字符串 Ⅱ（双指针）

朱雀 2022-09-03 00:23 154阅读 0赞

**1. 问题描述：**

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

**示例 1:**

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

**示例 2:**

输入: s = "abca"  
输出: true  
解释: 你可以删除c字符。

**示例 3:**

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

**提示:**

1 <= s.length <= 10 ^ 5  
s 由小写英文字母组成  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/valid-palindrome-ii

**2. 思路分析：**

我们先考虑不需要删除字符的情况，判断一个字符串是否是回文串可以使用**双指针**来解决，声明两个指针i，j，一开始的时候指针i，j分别指向字符串最左边与最右边的位置，当指针i，j指向的字符相等的时候那么指针i往右走，指针j往前走，直到两个指针相遇为止。如果我们发现指针指向的两个字符不相等的时候那么需要考虑两种情况：

*  删掉指针i指向的字符
 *  删掉指针j指向的字符

对于第一种情况我们判断\[i + 1:j\]是否是回文串即可，对于第二种情况判断\[i:j - 1\]是否是回文串即可，只要满足一种情况那么返回True，否则肯定不满足题目的条件返回False。可以发现这样考虑肯定是可以求解出原问题的答案的，因为我们在枚举的时候当发现字符不相等的时候那么就可以将这两种情况判断出来。

**3. 代码如下：**

class Solution:
        # 判断区间[i:j]是否是回文串
        def check(self, s: str, i: int, j: int):
            while i < j:
                if s[i] != s[j]: return False
                i += 1
                j -= 1
            return True
    
        def validPalindrome(self, s: str) -> bool:
            i, j = 0, len(s) - 1
            while i < j:
                if s[i] != s[j]:
                    # 其实就是检查区间[i + 1:j]与[i:j + 1]是否是回文串, 相当于是删除掉不相等的其中一个字符
                    if self.check(s, i + 1, j) or self.check(s, i, j - 1): return True
                    return False
                i += 1
                j -= 1
            return True