題目

難度：★★☆☆☆
類型：數(shù)組

給定一個(gè)非空字符串 s，最多刪除一個(gè)字符。判斷是否能成為回文字符串。

注意
字符串只包含從 a-z 的小寫字母。字符串的最大長(zhǎng)度是50000。

示例

示例 1
輸入: "aba"
輸出: True

示例 2
輸入: "abca"
輸出: True
解釋: 你可以刪除c字符。

解答

有這樣幾個(gè)規(guī)律需要考慮：

1. 一個(gè)回文串刪除一個(gè)元素后，依舊是回文串，不論該串長(zhǎng)度為奇數(shù)或偶數(shù)；

2. 定義雙指針，我們可以從兩頭向中間遍歷，當(dāng)遇到左右兩個(gè)不相同的字符時(shí)，我們無(wú)法判斷應(yīng)該刪除哪一個(gè)，可以考慮分別刪除，查看刪除哪一個(gè)字符后，剩余字符可以組成回文串，如果不論刪除哪一個(gè)，都無(wú)法組成回文串，說(shuō)明只刪除一個(gè)是不夠的。

編碼時(shí)需要注意下標(biāo)問(wèn)題。

class Solution:
    def validPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        is_palindrome = lambda s: s == s[::-1]                  # 判別輸入字符串s是否為回文串的函數(shù)

        while left <= right:                                    # 下標(biāo)滿足條件時(shí)
            if s[left] == s[right]:                             # 如果遇到相同元素
                left, right = left + 1, right - 1               # 繼續(xù)遍歷
            else:
                # 遇到不同元素時(shí)，查看分別跳過(guò)這兩個(gè)元素后能否組成回文串
                return is_palindrome(s[left+1: right+1]) or is_palindrome(s[left: right])
        return True

如有疑問(wèn)或建議，歡迎評(píng)論區(qū)留言~