题目

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

示例 1:
输入: “aba”
输出: True

示例 2:
输入: “abca”
输出: True
解释: 你可以删除c字符。

注意:

  1. 字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

    方案一（暴力法）

    1. class Solution:
    2.  def validPalindrome(self, s: str) -> bool:
    3.      if self.isPalindrome(s):
    4.          return True
    6.      for i in range(len(s)):
    7.          if self.isPalindrome(s[:i] + s[i+1:]):
    8.              return True
    10.      return False
    12.  def isPalindrome(self, s: str) -> bool:
    13.      length = len(s)
    14.      for i in range(length // 2):
    15.          if s[i] != s[length - i - 1]:
    16.              return False
    18.      return True
  • 时间复杂度 验证回文字符串 Ⅱ - 图1

  • leetcode 超时

    方案二（递归）

    1. class Solution:
    2.   def validPalindrome(self, s: str) -> bool:
    3.       def helper(s: str, isDeleted: bool) -> bool:
    4.           length = len(s)
    5.           if length <= 1:
    6.               return True
    8.           if s[0] == s[length - 1]:
    9.               return helper(s[1:length-1], isDeleted)
    10.           elif isDeleted: # 已经删除过字符了
    11.               return False
    12.           else:
    13.               return helper(s[1:], True) or helper(s[:length-1], True)
    15.       return helper(s, False)

    方案三（双指针）

    1. class Solution:
    2.   def validPalindrome(self, s: str) -> bool:
    3.       if len(s) <= 0:
    4.           return False
    6.       if s == s[::-1]:
    7.           return True
    9.       left = 0
    10.       right = len(s) - 1
    11.       while left < right:
    12.           if s[left] == s[right]:
    13.               left += 1
    14.               right -= 1
    15.           else:
    16.               s1 = s[:left] + s[left+1:]
    17.               s2 = s[:right] + s[right+1:]
    18.               if s1 == s1[::-1] or s2 == s2[::-1]:
    19.                   return True
    20.               else:
    21.                   return False

    参考链接

    https://leetcode-cn.com/explore/featured/card/2020-top-interview-questions/281/string/1258/