680. 验证回文字符串 Ⅱ

Difficulty

easy

Tags

双指针

字符串

URL

https://leetcode-cn.com/problems/valid-palindrome-ii/

Star

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

示例 1:


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

示例 2:


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

示例 3:


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

提示:

1 <= s.length <= 105

s 由小写英文字母组成

双指针

思路

按照相向指针来判断是非为回文串，当遇到不一样的字符串时，可以删除一个，那么该删除哪一个呢？两个均可以删除，所以此处代码出现的分支（类似二叉树）。

可以先找到不一样的地方，在分别判断。也可以采用递归的方式，采用递归的话，需要通过一个标志位来区分是否已经删除过字符了，该方法可以扩展为最多可以删除N个字符的题目。

题解


class Solution:
    def validPalindrome(self, s: str) -> bool:
        return self.isPalindrome(s=s, left=0, right=len(s)-1, flag=False)

    def isPalindrome(self, s, left, right, flag):
        if left >= right:
            return True

        if s[left] != s[right]:
            if flag:
                return False
            flag = True
            return self.isPalindrome(s, left+1, right, flag) or \
                    self.isPalindrome(s, left, right-1, flag)
        else:
            return self.isPalindrome(s, left+1, right-1, flag)