516 Longest Palindromic Subsequence
Last updated
Was this helpful?
Last updated
Was this helpful?
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:
Output:
One possible longest palindromic subsequence is "bbbb".
Example 2: Input:
Output:
One possible longest palindromic subsequence is "bb".
(1) DP
思路: 和Longest Common Subsequence一样的思路,求Longest Palindromic Subsequence只需要将原来string reverse(记为revS),然后对s和revS通过LCS算法即可
DP: 时间复杂度O(n^2), 空间复杂度O(n^2)