14.md

Longest Common Subseqence of 3 String

int find(string A, string B, string C, int i, int j, int k,vector<vector<vector<int>>>&dp)
    {
        if(i<0 || j<0 || k<0)
            return 0;
            
        if(dp[i][j][k]!=-1)
            return dp[i][j][k];
            
        if(A[i]==B[j] && A[i]==C[k])
            return dp[i][j][k]= 1+ find(A,B,C,i-1,j-1,k-1,dp);
            
        else
        {
            int l=find(A,B,C,i-1,j,k,dp);
            int c=find(A,B,C,i,j-1,k,dp);
            int s=find(A,B,C,i,j,k-1,dp);
            
            return dp[i][j][k]=max(l,max(c,s));
        }
    }

        int LCSof3 (string A, string B, string C, int n1, int n2, int n3)
        {
            // your code here
            
            vector<vector<vector<int>>>dp(n1+1,vector<vector<int>>(n2+1,vector<int>(n3+1,-1)));
            
            return find(A,B,C,n1-1,n2-1,n3-1,dp);
            }