题目大意：
验证回文字符串 III
给出一个字符串 s 和一个整数 k，请你帮忙判断这个字符串是不是一个 K 回文。
如果可以通过从字符串中删去最多 k 个字符将其转换为回文，该字符串是一个 K 回文。
示例 1：
输入：s = "abcdeca", k = 2 输出：true 解释：删除字符 “b” 和 “e”。
提示：
- 1 <= s.length <= 1000
- s 中只含有小写英文字母
- 1 <= k <= s.length
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1216
解题思路分析：
虽然本题是Hard级别，但如果动态规划题目做的多了，其实难度并不大，这道题就是标准的DP题目。之前的文章多次讲过，动态规划与递归加记忆数组的做法没有本质的区别，时间复杂度是相同的，由于本人感觉递归写法更容易理解，因此本题使用递归来解题。
我们定义一个递归方法helper(s, start, end)，代表将字符串s的start到end区间变成回文需要的次数。当start与end两位字符相同时，代表这两位不需要删除操作，因此：
helper(s, start, end) = helper(s, start+1, end-1);
如果start与end两位字符不同，我们则需要删除其中一个，删除哪一个好，要取决于全局递归结束后哪一个使用的删除操作少。故：
helper(s, start, end) = min(helper(s, start+1, end),
helper(s, start, end-1));最后我们再定义一个记忆数组memo[][]，防止重复计算。memo[i][j]代表将字符串[i,j]区间变成回文的操作次数。最终memo[0][s.length()-1]即为：将整个字符串变成回文所需要的操作次数，如果这个结果小于等于K则返回true，反之放回false。
实现代码：
Integer[][] memo; // 记忆数组
public boolean isValidPalindrome(String s, int k) {
// 初始化记忆数组
memo = new Integer[s.length()][s.length()];
return helper(s, 0, s.length()-1) <=k;
}
int helper(String s, int start, int end){
// 如果区间长度小于等于1，说明已经是回文，无需操作
if(end<=start) return 0;
// 如果记忆数组存在该区间的解，直接返回
if(memo[start][end]!=null) return memo[start][end];
int res; // 返回结果
// 如果当前两位的字符相同
if(s.charAt(start)==s.charAt(end)){
res = helper(s, start+1, end-1);
}else{ // 如果当前两位的字符不同
res = 1+Math.min(helper(s,start+1,end),
helper(s,start,end-1));
}
// 将计算结果保存至记忆数组
memo[start][end]=res;
return res;
}本题解法执行时间为12ms
Runtime: 12 ms, faster than 31.66% of Java online submissions for Valid Palindrome III.
Memory Usage: 36.3 MB, less than 100.00% of Java online submissions for Valid Palindrome III.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1216-valid-palindrome-iii-解题思路分析/