Longest Palindromic Subsequence
Given a String, find the longest palindromic subsequence.
- Time : O(n^2)
- Space : O(n^2)
c++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 longestPalinSubseq(string A) {
memset(dp, -1, sizeof dp);
return helper(A, 0, A.length() - 1);
}
|
