LeetCode 1216. 验证回文字符串 III（DP）

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

给出一个字符串 s 和一个整数 k，请你帮忙判断这个字符串是不是一个「K 回文」。

所谓「K 回文」：如果可以通过从字符串中删去最多 k 个字符将其转换为回文，那么这个字符串就是一个「K 回文」。

示例： 输入：s = "abcdeca", k = 2 输出：true 解释：删除字符 “b” 和 “e”。提示： 1 <= s.length <= 1000 s 中只含有小写英文字母 1 <= k <= s.length

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 类似题目：LeetCode 516. 最长回文子序列（动态规划）

求最长回文子序长度，跟上题一样的本质

class Solution { public:bool isValidPalindrome(string s, int k) {int i, j, n = s.size();vector<vector<int>> dp(n,vector<int>(n,0));for(i = 0; i < n; ++i)dp[i][i] = 1;for(j = 0; j < n; ++j){for(i = j-1; i >= 0; --i)//区间从小往大，所以逆序{if(s[i] == s[j])dp[i][j] = dp[i+1][j-1]+2;elsedp[i][j] = max(dp[i+1][j], dp[i][j-1]);}}return n-dp[0][n-1] <= k;} };

或者

class Solution { public:bool isValidPalindrome(string s, int k) {int i, j, n = s.size();vector<vector<int>> dp(n,vector<int>(n,0));for(i = 1; i < n; ++i)dp[i-1][i] = s[i-1]==s[i] ? 0 : 1;//两个字符不一样，需要删除1个才是回文for(j = 0; j < n; ++j){for(i = j-1; i >= 0; --i)//区间从小往大，所以逆序{if(s[i] == s[j])dp[i][j] = dp[i+1][j-1];elsedp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]);}}return dp[0][n-1] <= k;} };

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 1216. 验证回文字符串 III（DP）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。