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)


Last updated

Was this helpful?