Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
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.
"ace" is a subsequence of "abcde".A common subsequence of two strings is a subsequence that is common to both strings.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.
Longest Common Subsequence - LeetCode
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
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(!i||!j)
dp[i][j] = 0;
else if(text1[i-1]==text2[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
};
Time and Space Complexity of the above implementation is O(mn)
// Following code snippet is used to print LCS
int index = L[m][n];
// Create a character array to store the lcs string
char lcs[index+1];
lcs[index] = '\\0'; // Set the terminating character
// Start from the right-most-bottom-most corner and
// one by one store characters in lcs[]
int i = m, j = n;
while (i > 0 && j > 0)
{
// If current character in X[] and Y are same, then
// current character is part of LCS
if (X[i-1] == Y[j-1])
{
lcs[index-1] = X[i-1]; // Put current character in result
i--; j--; index--; // reduce values of i, j and index
}
// If not same, then find the larger of two and
// go in the direction of larger value
else if (L[i-1][j] > L[i][j-1])
i--;
else
j--;
}
// Print the lcs
cout << "LCS of " << X << " and " << Y << " is " << lcs;
One important observation in the simple implementation is, in each iteration of outer loop we only, need values from all columns of previous row. So there is no need of storing all rows in our DP matrix, we can just store two rows at a time and use them, in that way used space will reduce from L[m+1][n+1] to L[2][n+1]. Below is the implementation of above idea.
https://www.youtube.com/watch?v=Iuw2nOvYW20&ab_channel=CodeLibrary
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
vector<vector<int>> dp(2,vector<int>(n+1,0));
// Inside the loop just replace i with i%2 and i-1 with (i+1)%2
for(int i=0;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
if(!i||!j)
dp[i%2][j] = 0;
else if(text1[i-1]==text2[j-1])
dp[i%2][j] = 1 + dp[(i+1)%2][j-1];
else
dp[i%2][j] = max(dp[(i+1)%2][j],dp[i%2][j-1]);
}
}
return dp[m%2][n];
}
};