680. Valid Palindrome II

680. Valid Palindrome II

這一題是 125. Valid Palindrome 的變形，考的是如果說最多可以修改一個字元，那是否可以形成回文？

在 LeetCode 很多的題目裡面，有時候修改和刪除其實是等價的（參考編輯距離的題目 72. Edit Distance）

例如：

abca 我們把 b 改成 c 或是 c 改成 b 又或是把 b 刪掉或把 c 刪掉，都可以成為回文。其實有點像是容錯的概念，又換句話說就是我們乾脆跳過這個檢查點好了。

這一題我們會使用遞迴來做，會使用遞迴來做的原因是因為我們就不用花大量的精力，去判斷我們是要給右指針跳過，或是左指針跳過，在這裏，我們也可以使用一個 bool 來判斷是不是已經修改過了。

class Solution:
    def validPalindrome(self, s: str) -> bool:

        def isValidPalindrome(left, right, modified):
            while left <= right:
                if s[left] != s[right]:
                    if modified:
                        return False
                    else:
                        return isValidPalindrome(left + 1, right, True) or isValidPalindrome(left, right - 1, True)
                left += 1
                right -= 1
            return True

        return isValidPalindrome(0, len(s) - 1, False)

其實這個布林值也可用一個計數器來代替，去計算我們最多可以修改 k 個值。

class Solution:
    def validPalindrome(self, s: str) -> bool:

        def isValidPalindrome(left, right, k):
            while left <= right:
                if s[left] != s[right]:
                    if k <= 0:
                        return False
                    else:
                        return isValidPalindrome(left + 1, right, k - 1) or isValidPalindrome(left, right - 1, k - 1)
                left += 1
                right -= 1
            return True

        return isValidPalindrome(0, len(s) - 1, 1)