Longest Common Subsequence ( Three Approaches )

Longest Common Subsequence

LCS Problem Statement: Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”.

If S1 and S2 are the two given sequences then, Z is the common subsequence of S1 and S2 if Z is a subsequence of both S1 and S2. Furthermore, Z must be a strictly increasing sequence of the indices of both S1 and S2.

For example-

S1 = {B, C, D, A, A, C, D}

S2 = {A, C, D, B, A, C}

{C, D, A, C} is the longest common subsequence.

LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3.
LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

The naive solution for this problem is to generate all subsequences of both given sequences and find the longest matching subsequence. This solution is exponential in term of time complexity.

Consider the input strings “ABCDGH” and “AEDFHR. Last characters do not match for the strings. So length of LCS can be written as:
LCS(“ABCDGH”, “AEDFHR”) = MAX ( LCS(“ABCDG”, “AEDFHR”), LCS(“ABCDGH”, “AEDFH”) ).

class Solution {
public:
    int solve(string s1,string s2,int i,int j){
        if(i<0 || j<0)return 0;
        if(s1[i]==s2[j])return 1+solve(s1,s2,i-1,j-1);
        return max(solve(s1,s2,i-1,j),solve(s1,s2,i,j-1));
    }
    
    int longestCommonSubsequence(string s1, string s2) {
        return solve(s1,s2,s1.length()-1,s2.length()-1);
    }
};


class Solution {
public:
    int solve(string &s1,string &s2,int i,int j,vector<vector<int>>&dp){
        if(i<0 || j<0)return 0;
        if(dp[i][j])return dp[i][j];
        if(s1[i]==s2[j])return dp[i][j]=1+solve(s1,s2,i-1,j-1,dp);
        return dp[i][j]= max(solve(s1,s2,i-1,j,dp),solve(s1,s2,i,j-1,dp));
    }
    
    int longestCommonSubsequence(string s1, string s2) {
        vector<vector<int>>dp(s1.length(),vector<int>(s2.length(),0));
        return solve(s1,s2,s1.length()-1,s2.length()-1,dp);
    }
};


class Solution {
public:
    
    int longestCommonSubsequence(string s1, string s2) {
        vector<vector<int>>dp(s1.length()+1,vector<int>(s2.length()+1,0));
        
        for(int i=0; i<=s1.length(); i++){
            for(int j=0; j<=s2.length(); j++){
                if(i==0 || j==0)dp[i][j]=0;
                else if(s1[i-1]==s2[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[s1.length()][s2.length()];
        
    }
};