DEV Community

Carnato
Carnato

Posted on

Longest common sequence

this method is Memoization in dp

class Solution {
public:
   int dp[1001][1001];
     int lcs(string &text1,string &text2,int m,int n)
     {
         if(dp[m][n]!=-1) return dp[m][n];

         if(n == 0 || m == 0) // Base case
            return 0;


         if(text1[m-1]==text2[n-1])
            return dp[m][n]=1+lcs(text1,text2,m-1,n-1);
         else
            return dp[m][n]=max(lcs(text1,text2,m-1,n),lcs(text1,text2,m,n-1));
     }

    int longestCommonSubsequence(string text1, string text2) {

    int m=text1.size();
    int n=text2.size();
        int result=0;
        memset(dp,-1,sizeof(dp));
        result=lcs(text1,text2,m,n);
        return result;



    }
};

## 
Enter fullscreen mode Exit fullscreen mode

Discussion (0)