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:

Input: s = "abcdeca", k = 2
Output: true
Explanation: Remove 'b' and 'e' characters.

Example 2:

Input: s = "abbababa", k = 1
Output: true

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])（删除左或右字符）。

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)