广东网站建设哪家专业,外贸公司做网站,我的世界做封面网站,俄罗斯乌克兰最新局势让字符串成为回文串的最少插入次数
题目链接#xff1a;让字符串成为回文串的最少插入次数
题目
给你一个字符串 s #xff0c;每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。…让字符串成为回文串的最少插入次数
题目链接让字符串成为回文串的最少插入次数
题目
给你一个字符串 s 每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。 示例 1
输入s zzazz
输出0
解释字符串 zzazz 已经是回文串了所以不需要做任何插入操作。示例 2
输入s mbadm
输出2
解释字符串可变为 mbdadbm 或者 mdbabdm 。示例 3
输入s leetcode
输出5
解释插入 5 个字符后字符串变为 leetcodocteel 。提示
1 s.length 500s 中所有字符都是小写字母。 解法
算法原理与解析
我们这题使用动态规划我们做这类题目可以分为以下五个步骤
状态显示状态转移方程初始化防止填表时不越界填表顺序返回值
状态显示 dp[i][j] 表⽰字符串 [i, j] 区域成为回⽂⼦串的最少插⼊次数。 状态转移方程 当⾸尾两个元素「相同」的时候也就是 s[i] s[j] 那么 [i, j] 区间内成为回⽂⼦串的最少插⼊次数取决于 [i 1, j - 1] 区间内成为回⽂⼦串的最少插⼊次数 若 i j 或 i j - 1 [i 1, j - 1] 不构成合法区间此时只有 1 ~ 2 个相同的字符 [i, j] 区间⼀定是回⽂⼦串成为回⽂⼦串的最少插⼊次数是 0。 此时 dp[i][j] i j - 1 ? 0 : dp[i 1][j - 1] 当⾸尾两个元素「不相同」的时候也就是 s[i] ! s[j] 此时可以在区间最右边补上⼀个 s[i] 需要的最少插⼊次数是 [i 1, j] 成为回⽂⼦串的最少插⼊次数 本次插⼊即 dp[i][j] dp[i 1][j] 1 此时可以在区间最左边补上⼀个 s[j] 需要的最少插⼊次数是 [i, j 1] 成为回⽂⼦串的最少插⼊次数 本次插⼊即 dp[i][j] dp[i][j 1] 1 综上所述状态转移⽅程为 当 s[i] s[j] 时 dp[i][j] i j - 1 ? 1 : dp[i 1][j - 1] 。 当 s[i] ! s[j] 时 dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1。 初始化防止填表时不越界 根据「状态转移⽅程」没有不能递推表⽰的值。⽆需初始化。 填表顺序 根据「状态转移」我们发现在 dp 表所表⽰的矩阵中 dp[i 1] 表⽰下⼀⾏的位置 dp[j - 1] 表⽰前⼀列的位置。因此我们的填表顺序应该是「从下往上填写每⼀⾏」「每⼀ ⾏从左往右」。 返回值 根据「状态表⽰」我们需要返回 [0, n -1] 区域上成为回⽂⼦串的最少插⼊次数因此需要 返回 dp[0][n - 1] 。 代码实现
class Solution {
public:int minInsertions(string s) {int n s.size();vectorvectorint dp(n, vectorint(n)); // 表示[i,j]位置成为回文串最少的插入数据// 填表从下到上从左到右for (int i n - 1; i 0; i--){for (int j i 1; j n; j){if (s[i] s[j]) { dp[i][j] i 1 j ? dp[i 1][j - 1] : 0; }else { dp[i][j] min(dp[i 1][j], dp[i][j - 1]) 1; }}}return dp[0][n - 1];}
};
