Sponsored
Sponsored
Use a 2D table to keep track of the longest palindromic subsequence. The idea is to fill out this table by solving smaller subproblems and using their results to build up solutions to bigger ones.
The table, dp[i][j], will store the length of the longest palindromic subsequence in s[i...j]. Start by assuming that each character is a palindrome of length 1, and fill the table based on whether the characters at the current indices are the same.
Time Complexity: O(n^2), where n is the length of the string, because we need to fill an n x n table.
Space Complexity: O(n^2), for the same reason due to the dp table.
1def longestPalindromeSubseq(s: str) -> int:
2 n = len(s)
3 dp = [[0] * n for _ in range(n)]
4 for i in range(n - 1, -1, -1):
5 dp[i][i] = 1
6 for j in range(i + 1, n):
7 if s[i] == s[j]:
8 dp[i][j] = dp[i + 1][j - 1] + 2
9 else:
10 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
11 return dp[0][n - 1]
12
13if __name__ == "__main__":
14 print(longestPalindromeSubseq("bbbab"))Python's list comprehension is used to initialize the dp table, and the algorithm fills in the table similarly to other implementations.
This approach defines a recursive function that explores all potential palindromic subsequences, using memoization to store results of overlapping subproblems, thereby avoiding redundant calculations. The function checks if the characters at current indices are equal and proceeds based on that, with memoization avoiding recalculations.
Time Complexity: O(n^2), where n is the length of the string due to memoization.
Space Complexity: O(n^2) for the memoization table.
1#include <iostream>
#include <vector>
using namespace std;
class Solution {
vector<vector<int>> memo;
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
memo.resize(n, vector<int>(n, -1));
return helper(s, 0, n - 1);
}
int helper(string &s, int l, int r) {
if (l > r) return 0;
if (l == r) return 1;
if (memo[l][r] != -1) return memo[l][r];
if (s[l] == s[r]) {
memo[l][r] = 2 + helper(s, l + 1, r - 1);
} else {
memo[l][r] = max(helper(s, l + 1, r), helper(s, l, r - 1));
}
return memo[l][r];
}
};
int main() {
Solution solution;
cout << solution.longestPalindromeSubseq("bbbab") << endl;
return 0;
}C++ implementation using a vector for memoization, aligning with typical approaches of recursive solutions in C++ by utilizing stack memory efficiently for recursive calls.