LeetCode 1312. Minimum Insertion Steps to Makea String Palindrome

, , , , , ,

Question

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we don't need any insertions.

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

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

Input: s = "no"
Output: 1

Input: s = "g"
Output: 0

Solution

Actually it is the Dynamic Programming question, becasue we have to see the first char is equal to the last char and then become the smaller question, and when we solve the smaller question, we can get the answer. We can define DP as following:

1
2
3
4
state: dp[n + 1][n + 1], dp[i][j] means how many steps we need to make s from i to j is palindrome
init: all equals to -1, it means we didn't cache anything.
func: when char[i] == char[j], we just need calculate the smaller case, which means dp[i][j] = dp[i + 1][j + 1]; If not, we have to consider which side we need to make it palindrome, so we have two choices, whether left or right. But it both cost a step. So, dp[i][j] = 1 + min (dp[i][j - 1](insert ch that equals char[j]), dp[i+1][j](insert char that equals(i))). 
result: dp[1][n]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// time:O(n^2) space:O(n^2)
public int minInsertions(String s) {
        if (s == null || s.length() <= 1) return 0;
        int n = s.length();
        int[][] memo = new int[n + 1][n + 1];
        for (int [] row : memo) {
            Arrays.fill(row, -1);
        }
        return dfs(s, 1, n, memo);
    }
    
    // dp[i, j] = 1 + Math.min(dp[i, j - 1], dp[i + 1, j])
    public int dfs(String s, int i, int j, int[][] memo) {
        if (i >= j) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int res = 0;
        if (s.charAt(i - 1) == s.charAt(j - 1)) {
            res = dfs(s, i + 1, j - 1, memo);
        } else {
            res = 1 + Math.min(dfs(s, i + 1, j, memo), dfs(s, i, j - 1, memo));
        }
        memo[i][j] = res;
        return memo[i][j];
    }

Reference