Title

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

示例 1:

輸入: “aba”
輸出: True

示例 2:

輸入: “abca”
輸出: True
解釋: 你可以刪除c字符。

Solve

貪心算法：

考慮最樸素的方法：首先判斷原串是否是回文串，如果是，就返回 true；如果不是，則枚舉每一個(gè)位置作為被刪除的位置，再判斷剩下的字符串是否是回文串。這種做法的漸進(jìn)時(shí)間復(fù)雜度是 O(n²) 的，會(huì)超出時(shí)間限制。

換一種想法：首先考慮如果不允許刪除字符，如何判斷一個(gè)字符串是否是回文串？

常見的做法是使用雙指針：定義左右指針，初始時(shí)分別指向字符串的第一個(gè)字符和最后一個(gè)字符，每次判斷左右指針指向的字符是否相同，如果不相同，則不是回文串；如果相同，則將左右指針都往中間移動(dòng)一位，直到左右指針相遇，則字符串是回文串。

在允許最多刪除一個(gè)字符的情況下，同樣可以使用雙指針，通過貪心算法實(shí)現(xiàn)。

初始化兩個(gè)指針 low 和 high 分別指向字符串的第一個(gè)字符和最后一個(gè)字符，每次判斷兩個(gè)指針指向的字符是否相同，如果相同，則更新指針，令 low = low + 1 和 high = high - 1，然后判斷更新后的指針范圍內(nèi)的子串是否是回文字符串；如果兩個(gè)指針指向的字符不同，則兩個(gè)字符中必須有一個(gè)被刪除，此時(shí)我們就分成兩種情況：即刪除左指針對應(yīng)的字符，留下子串 s[low + 1], s[low + 1], …, s[high]，或者刪除右指針對應(yīng)的字符，留下子串 s[low], s[low + 1], …, s[high - 1]。當(dāng)這兩個(gè)子串中至少有一個(gè)是回文串時(shí)，就說明原始字符串刪除一個(gè)字符之后就以成為回文串。

Code

class Solution:def validPalindrome(s):if s == s[::-1]:return Truefor i in range(int(len(s) / 2)):if s[i] != s[-i - 1]:return s[i + 1:-i if -i else None] == s[i + 1:-i if -i else None][::-1] or s[i:-i - 1] == s[i:-i - 1][:: -1]

總結(jié)

以上是生活随笔為你收集整理的680. Valid Palindrome II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。