温州网站开发服务商,王也图片,wordpress 资讯类 模版,汕头企业网站公司文章目录1. 题目2. 解题1. 题目
给出一个字符串 s 和一个整数 k#xff0c;请你帮忙判断这个字符串是不是一个「K 回文」。
所谓「K 回文」#xff1a;如果可以通过从字符串中删去最多 k 个字符将其转换为回文#xff0c;那么这个字符串就是一个「K 回文」。
示例#x…
文章目录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();vectorvectorint dp(n,vectorint(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[i1][j-1]2;elsedp[i][j] max(dp[i1][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();vectorvectorint dp(n,vectorint(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[i1][j-1];elsedp[i][j] 1 min(dp[i1][j], dp[i][j-1]);}}return dp[0][n-1] k;}
};我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
