1312. Minimum Insertion Steps to Make a String Palindrome

Posted on Edited on In

1312. Minimum Insertion Steps to Make a String Palindrome

Description

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:

1
2
3
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.

Example 2:

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

Example 3:

1
2
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.

Hints/Notes

  • 2024/07/27
  • range dp
  • No solution from 0x3F

Solution

Language: C++

dfs:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> dp;

    int minInsertions(string s) {
        int n = s.size();
        dp.resize(n, vector<int>(n, -1));
        return dfs(0, n - 1, s);
    }

    int dfs(int start, int end, string& s) {
        if (start >= end) {
            return 0;
        }
        if (dp[start][end] != -1) {
            return dp[start][end];
        }
        int& res = dp[start][end];
        if (s[start] == s[end]) {
            res = dfs(start + 1, end - 1, s);
            return res;
        } else {
            res = min(dfs(start + 1, end, s) , dfs(start, end - 1, s)) + 1;
            return res;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        // state transition:
        // dp[i][j] is the number of insertion from i ~ j
        // base case: i == j => 0
        // if s[i] == s[j]
        //  => dp[i][j] = dp[i + 1][j - 1]
        // else
        //  => dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + 1
        // the direction: when calculating s[i][j], we need
        // the dp value with bigger i and smaller 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 - 1 ? 0 : dp[i + 1][j - 1];
                } else {
                    dp[i][j] = i + 1 > j - 1 ? 1 : min(dp[i][j - 1], dp[i + 1][j]) + 1;
                }
            }
        }
        return dp[0][n - 1];
    }
};