Formatted question description: https://leetcode.ca/all/1312.html
1312. Minimum Insertion Steps to Make a String Palindrome (Hard)
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 don't 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".
Example 4:
Input: s = "g" Output: 0
Example 5:
Input: s = "no" Output: 1
Constraints:
1 <= s.length <= 500- All characters of
sare lower case English letters.
Related Topics:
Dynamic Programming
Solution 1. DP
This problem is similar to “given two strings s and t, count how many insertions are needed to make them the same”.
In this problem, t is the reversed s.
Let dp[i][j] be the minimum insertions needed to make s[0..(i-1)] and t[0..(j-1)] the same.
dp[i][j] = dp[i-1][j-1] If s[i-1] == t[j-1]
= 1 + min(dp[i-1][j], dp[i][j-1]) If s[i-1] != t[j-1]
dp[0][i] = dp[i][0] = i
The answer of this problem is dp[N][N] / 2.
// OJ: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
int minInsertions(string s) {
int N = s.size();
string t(s.rbegin(), s.rend());
vector<vector<int>> dp(N + 1, vector<int>(N + 1));
for (int i = 0; i <= N; ++i) {
for (int j = 0; j <= N; ++j) {
if (i == 0 || j == 0) dp[i][j] = i + j;
else if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[N][N] / 2;
}
};
Solution 2. DP + Space Optimization
Since dp[i][j] is only dependent on dp[i-1][j-1], dp[i-1][j] and dp[i][j-1], we can reduce the space of dp array from N * N to 1 * N with a temporary variable storing dp[i-1][j-1].
// OJ: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
int minInsertions(string s) {
int N = s.size();
vector<int> dp(N + 1);
for (int i = 0; i <= N; ++i) {
int prev;
for (int j = 0; j <= N; ++j) {
int cur = dp[j];
if (i == 0 || j == 0) dp[j] = i + j;
else if (s[i - 1] == s[N - j]) dp[j] = prev;
else dp[j] = 1 + min(dp[j], dp[j - 1]);
prev = cur;
}
}
return dp[N] / 2;
}
};;
Solution 3. Longest Palindrome Subsequence
If we know the length of the longest palindrome subsequence of s is M, then the answer to this problem would be s.size() - M.
So we can reuse the solution to 516. Longest Palindromic Subsequence (Medium).
// OJ: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/
// Time: O(N^2)
// Space: O(N)
class Solution {
int longestPalindromeSubseq(string &s) {
int N = s.size();
vector<int> dp(N + 1);
for (int i = 1; i <= N; ++i) {
int prev = 0;
for (int j = 1; j <= N; ++j) {
int cur = dp[j];
if (s[i - 1] == s[N - j]) dp[j] = 1 + prev;
else dp[j] = max(dp[j], dp[j - 1]);
prev = cur;
}
}
return dp[N];
}
public:
int minInsertions(string s) {
return s.size() - longestPalindromeSubseq(s);
}
};
Java
-
class Solution { public int minInsertions(String s) { if (s.length() <= 1) return 0; StringBuffer sb = new StringBuffer(s); sb.reverse(); String reverseStr = sb.toString(); int longestCommonSubsequence = longestCommonSubsequence(s, reverseStr); return s.length() - longestCommonSubsequence; } public int longestCommonSubsequence(String str1, String str2) { int length1 = str1.length(), length2 = str2.length(); int[][] dp = new int[length1 + 1][length2 + 1]; for (int i = 1; i <= length1; i++) { char c1 = str1.charAt(i - 1); for (int j = 1; j <= length2; j++) { char c2 = str2.charAt(j - 1); if (c1 == c2) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); } } int commonLength = dp[length1][length2]; return commonLength; } } -
// OJ: https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/ // Time: O(N^2) // Space: O(N^2) class Solution { public: int minInsertions(string s) { int N = s.size(); string t(s.rbegin(), s.rend()); vector<vector<int>> dp(N + 1, vector<int>(N + 1)); for (int i = 0; i <= N; ++i) { for (int j = 0; j <= N; ++j) { if (i == 0 || j == 0) dp[i][j] = i + j; else if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1]; else dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]); } } return dp[N][N] / 2; } }; -
# 1312. Minimum Insertion Steps to Make a String Palindrome # https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/ class Solution: def lps(self, start, end, s, mem): if start == end: return 1 if start > end: return 0 if mem[start][end]: return mem[start][end] mem[start][end] = 2 + self.lps(start+1, end-1, s, mem) if s[start] == s[end] else max(self.lps(start, end-1, s, mem), self.lps(start+1, end, s, mem)) return mem[start][end] def minInsertions(self, s: str) -> int: n = len(s) mem = [[0]*n for _ in range(n)] return n - self.lps(0, n-1, s, mem)