Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
“bbbab”
Output:
4One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:
“cbbd”
Output:
2
One possible longest palindromic subsequence is “bb”.Constraints:
1 <= s.length <= 1000
s consists only of lowercase English letters.
Compute the Longest Palindromic Subsequence using Dynamic Programming Algorithm
Given a function F(l, r) to store the longest palindrome subsequence between index l and r, we then can compute the function based on the following conditions:
because any single character is a palindrome.
when l is larger than r, .
when ,
Otherwise, .
Given that we have DP (Dynamic Programming) equation, it is easy to implement it with a top-down approach i.e. Recursion with Memoization. See following C++ DP code using Two-Dimensional unordered_map (hash map).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public: int longestPalindromeSubseq(string s) { unordered_map<int, unordered_map<int, int>> memo; function<int(int, int)> dp = [&](int left, int right) { if (left == right) { return 1; } if (left > right) { return 0; } if (memo.count(left) && memo[left].count(right)) { return memo[left][right]; } if (s[left] == s[right]) { return memo[left][right] = 2 + dp(left + 1, right - 1); } return memo[left][right] = max(dp(left + 1, right), dp(left, right - 1)); }; return dp(0, static_cast<int>(s.size()) - 1); } }; |
class Solution { public: int longestPalindromeSubseq(string s) { unordered_map<int, unordered_map<int, int>> memo; function<int(int, int)> dp = [&](int left, int right) { if (left == right) { return 1; } if (left > right) { return 0; } if (memo.count(left) && memo[left].count(right)) { return memo[left][right]; } if (s[left] == s[right]) { return memo[left][right] = 2 + dp(left + 1, right - 1); } return memo[left][right] = max(dp(left + 1, right), dp(left, right - 1)); }; return dp(0, static_cast<int>(s.size()) - 1); } };
In Python, we can annoate the function with @lru_cache that allows to cache the intermediate values of DP automatically.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution: def longestPalindromeSubseq(self, s: str) -> int: @lru_cache(None) def dp(l, r): if l > r: return 0 if l == r: return 1 if s[l] == s[r] else 0 if s[l] == s[r]: return 2 + dp(l + 1, r - 1) return max(dp(l + 1, r), dp(l, r - 1)) return dp(0, len(s) - 1) |
class Solution: def longestPalindromeSubseq(self, s: str) -> int: @lru_cache(None) def dp(l, r): if l > r: return 0 if l == r: return 1 if s[l] == s[r] else 0 if s[l] == s[r]: return 2 + dp(l + 1, r - 1) return max(dp(l + 1, r), dp(l, r - 1)) return dp(0, len(s) - 1)
Time complexity is O(N^2) i.e. N^2 pairs of (l, r) and space complexity is also O(N^2).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Confusing Number Validation Algorithm
Next Post: Construct a Spiral Matrix using Simulation Algorithm