原文链接: https://leetcode-cn.com/problems/valid-palindrome-ii

英文原文

Given a string s, return true if the s can be palindrome after deleting at most one character from it.

 

Example 1:

Input: s = "aba"
Output: true

Example 2:

Input: s = "abca"
Output: true
Explanation: You could delete the character 'c'.

Example 3:

Input: s = "abc"
Output: false

 

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.

中文题目

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

 

示例 1:

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

示例 2:

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

示例 3:

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

 

提示:

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

通过代码

高赞题解

思路来源

题目问我们最多删除一个字符的情况下是否可以构成回文字符串，第一反应是逐个删除各个字符看剩下的字符串是否为回文串，但是这个时间复杂度是 O(N ^ 2)，题目给出的字符串的长度最大为 50000 ，此做法会超时。

回文串的特点是左右对称。假如有两个指针从字符串的两端同时向中间走：如果遇到的元素相等，则该相等的元素是最终回文字符串的一部分；如果遇到的元素不等，则认为此时遇到了构建回文字符串的「障碍」，应当进行处理，处理方式见下文。

初版方案

当左右两个指针遇到不等的元素时，按照题目最原本的意思，我们处理的方式是删除 左指针指向的字符 或者 右指针指向的字符，判断 剩余的所有字符 是否可以构成回文串。

我们观察一下题目给出的示例 2：

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

如果左右指针从两端同时向中间走，那么：

第一步：
a       b       c       a
|                       |
left                  right

第二步：
a       b       c       a
        |       |
        left  right

第一步，左右指针遇到的元素相等，继续向中间走；
第二步，左右指针遇到的元素不等，则必须进行处理：我们必须删除其中的一个字符，然后再判断 剩余的所有字符 是否是回文串。

删除 b：
a       c       a

或者，  删除 c：
a       b       a

即判断 aca 或者 aba 是否为回文字符串。

如果删除一个字符后，剩余的全部字符构成字符串 是回文字符串，那么就满足题意。

本方案的时间复杂度是：O(N)；由于我判断是否回文使用了 [::-1] 翻转形成了新字符串，所以空间复杂度是O(N)。如果不通过翻转的方式来判断，空间复杂度可以降到O(1)。

[]
class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        isPalindrome = lambda s: s == s[::-1]
        strPart = lambda s, x: s[:x] + s[x + 1:]
        left = 0
        right = len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return isPalindrome(strPart(s, left)) or isPalindrome(strPart(s, right))
            left += 1
            right -= 1
        return True

进阶方案

我们注意到「初版方案」中，在找到第一个不相等的元素后，删除了不相等的一个元素，判断 剩余的所有字符 是不是回文字符串。这个做法和题目最原本的意思完全一致。是否可以简化呢？

分析发现，在找到不相等的元素时，[0, left) 和 (right, len(s) - 1] 这两部分已经判断过是回文的，因此不用再次判断。只用判断 [left, right] 区间中的字符串，即删除 left 或者 right 指向的元素，剩余的区间 (left, right] 或者 [left, right) 是否为回文串。

若 (left, right] 或者 [left, right) 为回文串，则说明删除了一个字符可以构成回文串。

如题目的示例 2 ，当左右指针遇到了不等元素时，删除 left 或者 right 指向元素后， 我们只用判断 c 或者 b 是否为回文串。由于这两者是回文串，所以总体的字符串 s 删除 left 或者 right 指向元素也可以构成回文串。

本方案的时间复杂度是：O(N)；由于我判断是否回文使用了 [::-1] 翻转形成了新字符串，所以空间复杂度是O(N)。如果不通过翻转的方式来判断，空间复杂度可以降到O(1)。

这个方案在找到左右指针不等的字符后，所要检查的字符串更少。

[]
class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        isPalindrome = lambda x : x == x[::-1]
        left, right = 0, len(s) - 1
        while left <= right:
            if s[left] == s[right]:
                left += 1
                right -= 1
            else:
                return isPalindrome(s[left + 1 : right + 1]) or isPalindrome(s[left: right])
        return True

统计信息

通过次数	提交次数	AC比率
91843	228777	40.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
验证回文串	简单