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 <= 1000
1 <= text2.length <= 1000
- The input strings consist of lowercase English characters only.
A:
二维 DP
class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n1 = text1.length(); int n2 = text2.length(); vector<vector<int>> DP(n1+1, vector<int>(n2+1,0)); for(int i =0;i<n1;i++){ char ch1 = text1[i]; for(int j =0;j<n2;j++){ if(ch1==text2[j]){ DP[i+1][j+1] = DP[i][j] + 1; }else{ DP[i+1][j+1] = max(DP[i+1][j], DP[i][j+1]); } } } return DP[n1][n2]; } };
转换成 一维 (memory usage beat 68%)
class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n1 = text1.length(); int n2 = text2.length(); vector<int> DP(n2+1, 0); for(int i= 0;i<n1;i++){ char ch1 = text1[i]; vector<int> DP2(n2+1, 0); for(int j=1;j<=n2;j++){ if(ch1 == text2[j-1]){ DP2[j] = DP[j-1] + 1; }else{ DP2[j] = max(DP2[j-1], DP[j] ); } } DP = DP2; } return DP[n2]; } };
进一步的修改,就是不每次生成一个空间。而是reuse the DP space (memory usage beat 93%)
class Solution { public: int longestCommonSubsequence(string text1, string text2) { int n1 = text1.length(); int n2 = text2.length(); vector<vector<int>> DP(2, vector<int>(n2+1, 0)); for(int i= 1;i<=n1;i++){ char ch1 = text1[i-1]; for(int j=1;j<=n2;j++){ if(ch1 == text2[j-1]){ DP[i%2][j] = DP[(i-1)%2][j-1] + 1; }else{ DP[i%2][j] = max(DP[i%2][j-1], DP[(i-1)%2][j] ); } } } return DP[n1%2][n2]; } };
然而,空间复杂度还是 O (n1+ n2)
考虑转换成 O(1) 的空间
????可以吗? 我还不太会
No comments:
Post a Comment