Given two strings text1 and text2, return the length of their longest common subsequence.
A subsequence of a string is a new string generated from the original string with some characters(can be none) deleted without changing the relative order of the remaining characters. (eg, “ace” is a subsequence of “abcde” while “aec” is not). A common subsequence of two strings is a subsequence that is common to both strings.
If there is no common subsequence, return 0.
Example 1:
Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:
Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:
Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0.
Constraints:
1 <= text1.length <= 10001 <= text2.length <= 1000- The input strings consist of lowercase English characters only.
Solution: DP
Use dp[i][j] to represent the length of longest common sub-sequence of text1[0:i] and text2[0:j]
dp[i][j] = dp[i – 1][j – 1] + 1 if text1[i – 1] == text2[j – 1] else max(dp[i][j – 1], dp[i – 1][j])
Time complexity: O(mn)
Space complexity: O(mn) -> O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua, 16ms 14.9 MB class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.length(); int n = text2.length(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (text1[i] == text2[j]) dp[i + 1][j + 1] = dp[i][j] + 1; else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]); return dp[m][n]; } }; |
C++/V2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, 8ms, 8.8MB class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.length(); int n = text2.length(); vector<int> dp(n + 1); for (int i = 0; i < m; ++i) { int prev = 0; // dp[i][j] for (int j = 0; j < n; ++j) { int curr = dp[j + 1]; // dp[i][j + 1] if (text1[i] == text2[j]) // dp[i + 1][j + 1] = dp[i][j] + 1 dp[j + 1] = prev + 1; else // dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]) dp[j + 1] = max(curr, dp[j]); prev = curr; } } return dp[n]; // dp[m][n] } }; |
C++/V3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m = text1.length(); int n = text2.length(); vector<int> dp1(n + 1); vector<int> dp2(n + 1); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) if (text1[i] == text2[j]) dp2[j + 1] = dp1[j] + 1; else dp2[j + 1] = max(dp1[j + 1], dp2[j]); swap(dp1, dp2); } return dp1[n]; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment