Solution
This is a pretty standard problem solved using 2D DP. Define dp[i][j] as length of longest common subsequence (LCS) of first i characters of text1 and first j characters of text2. Assuming indices to be starting from 1, if text[i+1] == text2[j+1] then length of LCS of first i+1 chars of text1 and first j+1 chars of text2 would simply be 1 + dp[i][j]. When text1[i+1] != text2[j+1], dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]). To understand the second case better, consider the strings “abcde” and “ace”. LCS for substrings “ab” (i=2) and “a” (j=1) is 1 and LCS for substrings “a” (i=1) and “ac” (j=2) is 1. Now, when i=2 (“ab”) and j=2 (“ac”), text1[i] != text2[j] but the LCS is 1 because “ab” and “a” or “a” and “ac” have LCS of 1. Here is the complete table for better understanding:
"" a b c d e
"" 0 0 0 0 0 0
a 0 1 1 1 1 1
c 0 1 1 2 2 2
e 0 1 1 2 2 3
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.length(), len2 = text2.length();
if (len1 == 0 || len2 == 0)
return 0;
int dp[len1+1][len2+1];
memset(dp, 0, sizeof dp);
for (int i=1; i<=len1; i++) {
for (int j=1; j<=len2; j++) {
if (text1[i-1] == text2[j-1])
dp[i][j] = dp[i-1][j-1]+1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[len1][len2];
}
Time complexity: O(len1 * len2)
Space complexity: O(len1 * len2)