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.
1#include <iostream>
2#include <vector>
3#include <string>
4using namespace std;
5
6int minInsertions(string s) {
7 int n = s.length();
8 vector<vector<int>> dp(n, vector<int>(n, 0));
9 for (int len = 1; len < n; ++len) {
10 for (int i = 0, j = len; j < n; ++i, ++j) {
11 if (s[i] == s[j]) {
12 dp[i][j] = dp[i+1][j-1];
13 } else {
14 dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]);
15 }
16 }
17 }
18 return dp[0][n-1];
19}
20
21int main() {
22 cout << minInsertions("mbadm") << endl;
23 return 0;
24}In this C++ version, we utilize a 2D vector dp to store the minimal insertions needed for substrings. The logic is akin to the C solution.
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.
1def solve(s, left, right, dp):
2 if left >= right:
3 return 0
4 if dp[left][right] != -1:
5 return dp[left][right]
6 if s[left] == s[right]:
7 dp[left][right] = solve(s, left + 1, right - 1, dp)
8 else:
9 dp[left][right] = 1 + min(solve(s, left + 1, right, dp), solve(s, left, right - 1, dp))
10 return dp[left][right]
11
12def minInsertions(s):
13 n = len(s)
14 dp = [[-1] * n for _ in range(n)]
15 return solve(s, 0, n - 1, dp)
16
17print(minInsertions("mbadm"))The Python version employs recursion with memoization. A nested list dp is used to store already computed results, avoiding unnecessary calculations.