0680. 验证回文串 II

• 标签：贪心、双指针、字符串
• 难度：简单

题目链接

• 0680. 验证回文串 II - 力扣

题目大意

给定一个非空字符串 s。

要求：判断如果最多从字符串中删除一个字符能否得到一个回文字符串。

解题思路

题目要求在最多删除一个字符的情况下是否能得到一个回文字符串。最直接的思路是遍历各个字符，判断将该字符删除之后，剩余字符串是否是回文串。但是这种思路的时间复杂度是 $O(n^2)$，解答的话会超时。

我们可以通过双指针 + 贪心算法来减少时间复杂度。具体做法如下：

• 使用两个指针变量 left、right 分别指向字符串的开始和结束位置。

• 判断 s[left] 是否等于 s[right]。

  • 如果等于，则 left 右移、right左移。
  • 如果不等于，则判断 s[left: right - 1] 或 s[left + 1, right] 是为回文串。
    • 如果是则返回 True。
    • 如果不是则返回 False，然后继续判断。

• 如果 right >= left，则说明字符串 s 本身就是回文串，返回 True。

代码

class Solution:
    def checkPalindrome(self, s: str, left: int, right: int):
        i, j = left, right
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

    def validPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        while left < right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return self.checkPalindrome(s, left + 1, right) or self.checkPalindrome(s, left, right - 1)
        return True