# 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.

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 do not need any insertions.

Example 2:

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.

## Solutions

• class Solution {
private Integer[][] f;
private String s;

public int minInsertions(String s) {
this.s = s;
int n = s.length();
f = new Integer[n][n];
return dfs(0, n - 1);
}

private int dfs(int i, int j) {
if (i >= j) {
return 0;
}
if (f[i][j] != null) {
return f[i][j];
}
int ans = 1 << 30;
if (s.charAt(i) == s.charAt(j)) {
ans = dfs(i + 1, j - 1);
} else {
ans = Math.min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
}
return f[i][j] = ans;
}
}

• class Solution {
public:
int minInsertions(string s) {
int n = s.size();
int f[n][n];
memset(f, -1, sizeof(f));
function<int(int, int)> dfs = [&](int i, int j) -> int {
if (i >= j) {
return 0;
}
if (f[i][j] != -1) {
return f[i][j];
}
int ans = 1 << 30;
if (s[i] == s[j]) {
ans = dfs(i + 1, j - 1);
} else {
ans = min(dfs(i + 1, j), dfs(i, j - 1)) + 1;
}
return f[i][j] = ans;
};
return dfs(0, n - 1);
}
};

• class Solution:
def minInsertions(self, s: str) -> int:
@cache
def dfs(i: int, j: int) -> int:
if i >= j:
return 0
if s[i] == s[j]:
return dfs(i + 1, j - 1)
return 1 + min(dfs(i + 1, j), dfs(i, j - 1))

return dfs(0, len(s) - 1)

• func minInsertions(s string) int {
n := len(s)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
for j := range f[i] {
f[i][j] = -1
}
}
var dfs func(i, j int) int
dfs = func(i, j int) int {
if i >= j {
return 0
}
if f[i][j] != -1 {
return f[i][j]
}
ans := 1 << 30
if s[i] == s[j] {
ans = dfs(i+1, j-1)
} else {
ans = min(dfs(i+1, j), dfs(i, j-1)) + 1
}
f[i][j] = ans
return ans
}
return dfs(0, n-1)
}