1216：验证回文字符串 III（★）

2019-10-05 约 253 字预计阅读 1 分钟次阅读

力扣第 10 场双周赛第 4 题

题目

给出一个字符串 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

分析

本质是求最长回文子序列
区间 dp 递推即可

解答

1
2
3
4
5
6
7
8
9


class Solution:
    def isValidPalindrome(self, s: str, k: int) -> bool:
        n = len(s)
        dp = [[0]*n for _ in range(n)]
        for i in range(n-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, n):
                dp[i][j] = 2+dp[i+1][j-1] if s[i]==s[j] else max(dp[i+1][j], dp[i][j-1])
        return n - dp[0][-1] <= k

204 ms

目录

1216：验证回文字符串 III（★）

题目

分析

解答