class Solution {
public:
int longestPalindromeSubseq(string s) {
const int n = s.length();
// dp[i][j] := LPS's length in s[i..j]
dp.resize(n, vector<int>(n));
return lps(s, 0, n - 1);
}
private:
vector<vector<int>> dp;
int lps(const string& s, int i, int j) {
if (i > j)
return 0;
if (i == j)
return 1;
if (dp[i][j])
return dp[i][j];
if (s[i] == s[j])
dp[i][j] = 2 + lps(s, i + 1, j - 1);
else
dp[i][j] = max(lps(s, i + 1, j), lps(s, i, j - 1));
return dp[i][j];
}
};
leetcode
challenge
Here is the link for the problem:
https://leetcode.com/problems/longest-palindromic-subsequence/submissions/933388556/
Top comments (0)