LeetCode-680-驗證迴文字元串 Ⅱ

• 2020 年 11 月 15 日
• 筆記

給定一個非空字元串 s，最多刪除一個字元。判斷是否能成為迴文字元串。
image.png

解題思路：
判斷是否迴文字元串：isPalindrome = lambda x: x==x[::-1]，即將字元串x倒置，還和原來的一樣；
如何判斷刪除一個字元後還是迴文字元串？假設字元串s=’abccbca’，當用雙指針從兩端向中間遊走，如果兩指針所指字元不相等，考慮刪除其中之一，再判斷是否迴文字元串。
該例中當left=1和right=5時，刪除其中之一再判斷，只需判斷left和right之間的字元串是否迴文，生成的新的兩個字元串分別為刪除右邊字元：s[left:right]，刪除左邊字元：s[left+1:right+1]。
Python3程式碼：

class Solution:
def validPalindrome(self, s: str) -> bool:
left = 0
right = len(s)-1
isPalindrome = lambda x : x == x[::-1]

    while left<=right:
        if s[left] != s[right]:
            return isPalindrome(s[left:right]) or isPalindrome(s[left+1:right+1])
        else:
            left+=1
            right-=1
    return True