題目出處

680. Valid Palindrome II

難度

easy

個人範例程式碼 – two pointers

class Solution:
    def validPalindrome(self, s: str) -> bool:
        start, end = 0, len(s) - 1 
        while(start < end):
            if(s[start] == s[end]): # same
                start += 1
                end -= 1
            else: # not same, try cut one
                return self.is_palindrome(s, start+1, end) or self.is_palindrome(s, start, end-1) 

        return True

    def is_palindrome(self, s, start, end):
        while(start < end):
            if (s[start] == s[end]):
                start += 1
                end -= 1
            else:
                return False
        return True

算法說明

這題可以用比較聰明的作法，
我們既然都知道我們會需要「多次判斷」是否是「回文」，

我們可以先寫好判斷回文的 function 「is_palindrome」，
讓我們的主程式可以多次的去 call。

而刪除的概念可以理解為，如果我們找到兩端各一個「非相同的文字」，
我們就嘗試「左邊」與「右邊」都去掉嘗試判斷看看，
因為只要判斷一次刪除，因此如果回傳都沒有解，即為最終無解的情況。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

處理沒有 input 的狀況，內建 start < end 條件可以處理

Boundary conditions

start < end，交錯或等於就結束

Reference

• 有效回文 II · Valid Palindrome II