Problem
题目大意：找出最长回文子序列的长度。
https://leetcode.com/problems/longest-palindromic-subsequence/description/
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:
4
One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:
"cbbd"
Output:
2
One possible longest palindromic subsequence is “bb”.
Solution: DP
Time complexity: O(n^2)
Space complexity: O(n^2)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 102 ms class Solution { public: int longestPalindromeSubseq(string s) { const int n = s.length(); vector<vector<int>> dp(n, vector<int>(n, 0)); for (int l = 1; l <= n; ++l) for (int i = 0; i <= n - l; ++i) { int j = i + l - 1; if (i == j) { dp[i][j] = 1; continue; } dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2; } return dp[0][n - 1]; } }; |
Time complexity: O(n^2)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua // Running time: 28 ms class Solution { public: int longestPalindromeSubseq(string s) { const int n = s.length(); vector<int> dp0(n); // sols of len = l vector<int> dp1(n); // sols of len = l - 1 vector<int> dp2(n); // sols of len = l - 2 for (int l = 1; l <= n; ++l) { for (int i = 0; i <= n - l; ++i) { int j = i + l - 1; if (i == j) { dp0[i] = 1; continue; } if (s[i] == s[j]) dp0[i] = dp2[i + 1] + 2; else dp0[i] = max(dp1[i + 1], dp1[i]); } dp0.swap(dp1); dp2.swap(dp0); } return dp1[0]; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
""" Author: Huahua Running time: 1276 ms """ class Solution: def longestPalindromeSubseq(self, s): n = len(s) dp0 = [0] * n dp1 = [1] * n dp2 = [0] * n for l in range(2, n + 1): for i in range(0, n - l + 1): j = i + l - 1 if s[i] == s[j]: dp0[i] = dp2[i + 1] + 2 else: dp0[i] = max(dp1[i + 1], dp1[i]) dp0, dp1, dp2 = dp2, dp0, dp1 return dp1[0] |
C#
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Author: Huahua // Running time: 116 ms (beats 100%) public class Solution { public int LongestPalindromeSubseq(string s) { var n = s.Length; var dp0 = new int[n]; var dp1 = new int[n]; var dp2 = new int[n]; for (var l = 1; l <= n; ++l) { for (var i = 0; i <= n - l; ++i) { int j = i + l - 1; if (i == j) { dp0[i] = 1; continue; } if (s[i] == s[j]) dp0[i] = dp2[i + 1] + 2; else dp0[i] = Math.Max(dp1[i], dp1[i + 1]); } var tmp = dp2; dp2 = dp1; dp1 = dp0; dp0 = tmp; } return dp1[0]; } } |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment