Form a palindrome
Given a string, find the minimum number of characters to be inserted to convert it to palindrome.
For Example:
- ab: Number of insertions required is 1. bab or aba
- aa: Number of insertions required is 0. aa
- abcd: Number of insertions required is 3. dcbabcd
- Time : O(n^2)
- Space : O(n^2)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| class Solution { int dp[505][505]; int helper(string& S, int l, int r) { if(l > r) return 0; if(l == r) return 1; if(dp[l][r] != -1) return dp[l][r]; int& res = dp[l][r] = max(helper(S, l + 1, r), helper(S, l, r - 1)); if(S[l] == S[r]) res = max(res, 2 + helper(S, l + 1, r - 1)); return res; } public: int findMinInsertions(string S) { memset(dp, -1, sizeof dp); return S.length() - helper(S, 0, S.length() - 1); } };
|