0680._Valid_Palindrome_II.md

680. Valid Palindrome II

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/valid-palindrome-ii/description/

内容描述

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.

Example 1:
Input: "aba"
Output: True
Example 2:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.
Note:
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.

解题方案

思路 1

想直接来个 for loop，看看对应除去该index元素之后的字符串是否为 palindrome 即可

但是直接 Time Limit Exceeded

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        for i in range(len(s)):
            if s[:i] + s[i+1:] == s[i+1:][::-1] + s[:i][::-1]:
                return True
        return False

思路 2

我们先定义一个reverse变量作为字符串s的翻转版本，例如

s =       'abbbbbca'
reverse = 'acbbbbba'

然后我们从第一个字符开始比较，直到两边的字符不相等的时候，比如上面的例子我们就是index为1的时候不相等，所以i = 1，此时我们就会面临两个选择：

1. 我们可以舍弃s中index为i的这个元素看看是否可以使其成为palindrome，即让s变成'abbbbca'，然后我们可以通过s[i+1:n-i] == reverse[i:n-i-1]来判断
2. 我们可以舍弃reverse中index为i的这个元素（即s中index为n-1-i的这个元素），即让s变成'abbbbba'，我们可以通过s[i:n-1-i] == reverse[i+1:n-i]来判断

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        n = len(s)
        if n < 3:
            return True

        reverse = s[::-1]
        i = 0
        while i < len(s) and s[i] == reverse[i]:
            i += 1
        return s[i:n-1-i] == reverse[i+1:n-i] or s[i+1:n-i] == reverse[i:n-i-1]

思路 3

或者我们不搞reverse，直接在s上面原地判断即可

class Solution(object):
    def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        n = len(s)
        if n < 3:
            return True

        l, r = 0, n - 1
        while l < r and s[l] == s[r]:
            l += 1
            r -= 1
        if l >= r:
            return True
        else:
            return s[l+1:r+1] == s[l+1:r+1][::-1] or s[l:r] == s[l:r][::-1]