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
| 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)
|
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 {
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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | 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);
}
};
|
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
28 | 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)
}
|
Solution 2
| 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]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | 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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | 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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | 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]
}
|
Solution 3
1
2
3
4
5
6
7
8
9
10
11
12 | 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]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | 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];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | 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];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | 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]
}
|