# 1312. Minimum Insertion Steps to Make a String Palindrome

Given a string `s`. In one step you can insert any character at any index of the string.

Return  the minimum number of steps  to make `s` palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Example 1:

``````Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.
``````

Example 2:

``````Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".
``````

Example 3:

``````Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".
``````

Constraints:

• `1 <= s.length <= 500`
• `s` consists of lowercase English letters.

``````class Solution {
public:
int minInsertions(string s) {
int res = 0, n = s.size();
vector<vector<int>> dp(n, vector<int>(n));
for (int i = n - 1; i >= 0; --i) {
dp[i][i] = 1;
for (int j = i + 1; j < n; ++j) {
dp[i][j] = (s[i] == s[j]) ? (dp[i + 1][j - 1] + 2) : max(dp[i + 1][j], dp[i][j - 1]);
}
}
return n - dp[0][n - 1];
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1312

Longest Palindromic Subsequence

Minimum Number of Moves to Make Palindrome

https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/

https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/discuss/470706/JavaC%2B%2BPython-Longest-Common-Sequence

https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/discuss/470684/C%2B%2B-Simple-DP-(Memoization)-and-Bottom-up-with-O(n)-Space

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation