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:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not 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 <= 500s consists of lowercase English letters.
Solutions
Solution 1
PythonJavaC++Go
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)(code-box)
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;
}
}(code-box)
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);
}
};(code-box)
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)
}(code-box)
Solution 2
PythonJavaC++Go
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
f = [[0] * n for _ in range(n)]
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if s[i] == s[j]:
f[i][j] = f[i + 1][j - 1]
else:
f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1
return f[0][-1](code-box)
class Solution {
public int minInsertions(String s) {
int n = s.length();
int[][] f = new int[n][n];
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (s.charAt(i) == s.charAt(j)) {
f[i][j] = f[i + 1][j - 1];
} else {
f[i][j] = Math.min(f[i + 1][j], f[i][j - 1]) + 1;
}
}
}
return f[0][n - 1];
}
}(code-box)
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
int f[n][n];
memset(f, 0, sizeof(f));
for (int i = n - 2; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
if (s[i] == s[j]) {
f[i][j] = f[i + 1][j - 1];
} else {
f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
}
}
}
return f[0][n - 1];
}
};(code-box)
func minInsertions(s string) int {
n := len(s)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
}
for i := n - 2; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
f[i][j] = f[i+1][j-1]
} else {
f[i][j] = min(f[i+1][j], f[i][j-1]) + 1
}
}
}
return f[0][n-1]
}(code-box)
Solution 3
PythonJavaC++Go
class Solution:
def minInsertions(self, s: str) -> int:
n = len(s)
f = [[0] * n for _ in range(n)]
for k in range(2, n + 1):
for i in range(n - k + 1):
j = i + k - 1
if s[i] == s[j]:
f[i][j] = f[i + 1][j - 1]
else:
f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1
return f[0][n - 1](code-box)
class Solution {
public int minInsertions(String s) {
int n = s.length();
int[][] f = new int[n][n];
for (int k = 2; k <= n; ++k) {
for (int i = 0; i + k - 1 < n; ++i) {
int j = i + k - 1;
if (s.charAt(i) == s.charAt(j)) {
f[i][j] = f[i + 1][j - 1];
} else {
f[i][j] = Math.min(f[i + 1][j], f[i][j - 1]) + 1;
}
}
}
return f[0][n - 1];
}
}(code-box)
class Solution {
public:
int minInsertions(string s) {
int n = s.size();
int f[n][n];
memset(f, 0, sizeof(f));
for (int k = 2; k <= n; ++k) {
for (int i = 0; i + k - 1 < n; ++i) {
int j = i + k - 1;
if (s[i] == s[j]) {
f[i][j] = f[i + 1][j - 1];
} else {
f[i][j] = min(f[i + 1][j], f[i][j - 1]) + 1;
}
}
}
return f[0][n - 1];
}
};(code-box)
func minInsertions(s string) int {
n := len(s)
f := make([][]int, n)
for i := range f {
f[i] = make([]int, n)
}
for k := 2; k <= n; k++ {
for i := 0; i+k-1 < n; i++ {
j := i + k - 1
if s[i] == s[j] {
f[i][j] = f[i+1][j-1]
} else {
f[i][j] = min(f[i+1][j], f[i][j-1]) + 1
}
}
}
return f[0][n-1]
}(code-box)
