1312. Minimum Insertion Steps to Make a String Palindrome
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
int dp[501][501];
int lps(string& s, int l, int r) {
if(l > r) return 0;
if(dp[l][r] != -1) return dp[l][r];
if(l == r) return dp[l][r] = 1;
if(s[l] == s[r]) return dp[l][r] = lps(s, l + 1, r - 1) + 2;
return dp[l][r] = max(lps(s, l + 1, r), lps(s, l, r- 1));
}
public:
int minInsertions(string s) {
memset(dp, -1, sizeof(dp));
int plen = lps(s, 0, s.length() - 1);
return s.length() - plen;
}
};
|
