Sponsored
Sponsored
This approach utilizes dynamic programming to find the longest palindromic subsequence in the given string. The minimum number of insertions required is the difference between the length of the string and this subsequence. The idea is to consider characters from both ends of the string and make decisions accordingly using a DP table.
Time Complexity: O(n^2), where 'n' is the length of the string. This is due to the nested loops filling the DP table.
Space Complexity: O(n^2), as it uses a two-dimensional array for the DP table.
1def minInsertions(s):
2 n = len(s)
3 dp = [[0] * n for _ in range(n)]
4
In Python, we create a list of lists as our DP table. For each substring length, we determine the least insertions needed by comparing characters from both ends, adjusting counts based on matches or not.
This approach leverages a recursive function to explore all possibilities, but uses memoization to cache results of previously computed subproblems. This reduces redundant calculations.
Time Complexity: O(n^2)
Space Complexity: O(n^2) due to the memoization table.
1#include <vector>
#include <string>
using namespace std;
vector<vector<int>> dp;
int solve(const string &s, int left, int right) {
if (left >= right) return 0;
if (dp[left][right] != -1) return dp[left][right];
if (s[left] == s[right])
dp[left][right] = solve(s, left + 1, right - 1);
else
dp[left][right] = 1 + min(solve(s, left + 1, right), solve(s, left, right - 1));
return dp[left][right];
}
int minInsertions(string s) {
int n = s.length();
dp.resize(n, vector<int>(n, -1));
return solve(s, 0, n - 1);
}
int main() {
cout << minInsertions("mbadm") << endl;
return 0;
}In C++, a recursive function solve is utilized. Memoization is achieved using a 2D vector to store intermediate results, reducing redundant recursive calls.