深圳市门户网站建设哪家好,微信小程序案例源码,企业网站的建设目的,如何建CMS网站文章目录1. 题目2. 解题1. 题目
给你一个字符串 s #xff0c;每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1#xff1a;
输入#xff1a;s zzazz
输出每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
示例 1
输入s zzazz
输出0
解释字符串 zzazz 已经是回文串了所以不需要做任何插入操作。示例 2
输入s mbadm
输出2
解释字符串可变为 mbdadbm 或者 mdbabdm 。示例 3
输入s leetcode
输出5
解释插入 5 个字符后字符串变为 leetcodocteel 。示例 4
输入s g
输出0示例 5
输入s no
输出1提示
1 s.length 500
s 中所有字符都是小写字母。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 5. 最长回文子串动态规划 LeetCode 647. 回文子串DP LeetCode 1216. 验证回文字符串 IIIDP LeetCode 516. 最长回文子序列动态规划
dp[i][j] 区间 [i,j] 变成回文的最少操作次数
class Solution {
public:int minInsertions(string s) {int n s.size();vectorvectorint dp(n,vectorint(n, 0));for(int i 1; i n; i) {if(s[i-1] ! s[i])//初始化dp[i-1][i] 1;}for(int len 2; len n; len){for(int i 0; ilen n; i){int j ilen;if(s[i]s[j])dp[i][j] dp[i1][j-1];else{dp[i][j] min(2dp[i1][j-1], 1 min(dp[i1][j], dp[i][j-1]));}}}return dp[0][n-1];}
};88 ms 26.6 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
