Welcome to Subscribe On Youtube
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:
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 <= 500sconsists 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) }