文章目錄
- 1. 題目
- 2. 解題
1. 題目
給你一個字串 s ，每一次操作你都可以在字串的任意位置插入任意字符，
請你回傳讓 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. 驗證回文字串 III（DP）
LeetCode 516. 最長回文子序列（動態規劃）
dp[i][j]區間[i,j]變成回文的最少操作次數
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
vector<vector<int>> dp(n,vector<int>(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; i+len < n; i++)
{
int j = i+len;
if(s[i]==s[j])
dp[i][j] = dp[i+1][j-1];
else
{
dp[i][j] = min(2+dp[i+1][j-1], 1 + min(dp[i+1][j], dp[i][j-1]));
}
}
}
return dp[0][n-1];
}
};
88 ms 26.6 MB
我的CSDN博客地址 https://michael.blog.csdn.net/
長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/159727.html
標籤：其他