1216. 验证回文字符串 III

Difficulty
Hard
Tags
动态规划
URL
https://leetcode.cn/problems/valid-palindrome-iii/
Star
给出一个字符串 s 和一个整数 k，若这个字符串是不是一个「k 回文 」，则返回 true 。
如果可以通过从字符串中删去最多 k 个字符将其转换为回文，那么这个字符串就是一个「k 回文 」。
示例 1：
输入：s = "abcdeca", k = 2 输出：true 解释：删去字符 “b” 和 “e”。
示例 2:
输入：s = "abbababa", k = 1 输出：true
提示：
1 <= s.length <= 1000 s 中只含有小写英文字母 1 <= k <= s.length

法 1 动态规划

思路
把s翻转得到一个新串 s2， 问题就转化为 s 和 s2 最长公共子序列的长度， 那些缝隙中的就是要删除的字符。然后统计一下要删除的字符 的个数是否小于 k。
题解
class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        s1 = "#" + s
        s2 = "#" + s[::-1]

        dp = [[0] * len(s2) for _ in s1]
        
        for i in range(1, len(s1)):
            for j in range(1, len(s2)):
                if s1[i] == s2[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        # res 表示需要删除的最少字符
        res = len(s1) - dp[-1][-1] - 1

        # 回文串多删除几个还是回文串
        return res <= k