> For the complete documentation index, see [llms.txt](https://garylai.gitbook.io/algorithm-and-data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://garylai.gitbook.io/algorithm-and-data-structure/classic-problems/palindrome/valid-palindrome-ii.md).

# 680. Valid Palindrome II

[680. Valid Palindrome II](https://leetcode.com/problems/valid-palindrome-ii/)

這一題是 [125. Valid Palindrome](/algorithm-and-data-structure/classic-problems/palindrome/valid-palindrome.md) 的變形，考的是如果說最多可以修改一個字元，那是否可以形成回文？

在 LeetCode 很多的題目裡面，有時候修改和刪除其實是等價的（參考編輯距離的題目 [72. Edit Distance](/algorithm-and-data-structure/problems/dynamic-programming/edit-distance.md)）

例如：

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

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

```python
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 個值。

```python
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)
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://garylai.gitbook.io/algorithm-and-data-structure/classic-problems/palindrome/valid-palindrome-ii.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.