DEV Community

Vishal Yadav
Vishal Yadav

Posted on

3 3

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

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more