> For the complete documentation index, see [llms.txt](https://nataliekung.gitbook.io/ladder_code/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://nataliekung.gitbook.io/ladder_code/meta-2025/1216.-valid-palindrome-iii.md).

# 1216. Valid Palindrome III

Given a string `s` and an integer `k`, return `true` if `s` is a `k`**-palindrome**.

A string is `k`**-palindrome** if it can be transformed into a palindrome by removing at most `k` characters from it.

 

**Example 1:**

<pre><code><strong>Input: s = "abcdeca", k = 2
</strong><strong>Output: true
</strong><strong>Explanation: Remove 'b' and 'e' characters.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: s = "abbababa", k = 1
</strong><strong>Output: true
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= s.length <= 1000`
* `s` consists of only lowercase English letters.
* `1 <= k <= s.length`

分析

**方法一：记忆化搜索（DFS + Memoization）**

* **核心思想**：用递归尝试删除字符，并通过缓存避免重复计算。
* **优化点**：
  * 添加 `@lru_cache` 装饰器缓存递归结果。
  * 提前检查剩余字符串是否为回文。

**方法二：动态规划（DP）**

* **核心思想**：计算最少需要删除多少字符才能使 `s` 变成回文，然后判断是否 `<= k`。
* **状态定义**：
  * `dp[i][j]`：将 `s[i..j]` 变成回文需要删除的最少字符数。
* **转移方程**：
  * 如果 `s[i] == s[j]`，则 `dp[i][j] = dp[i+1][j-1]`（无需删除）。
  * 否则，`dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])`（删除左或右字符）。

```python3
from functools import lru_cache


class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        @lru_cache(maxsize=None)
        def dfs(l,r,k):
            if l >=r:
                return True
            elif s[l] == s[r]:
                return dfs(l+1,r-1,k)
            elif k > 0:
                return dfs(l+1,r,k-1) or dfs(l,r-1,k-1)
            else:
                return False
        return dfs(0,len(s)-1,k)



```