DEV Community

Carnato
Carnato

Posted on

longest common subsequence

Tabulation

class Solution {
public:

    int longestCommonSubsequence(string text1, string text2) {

    int m=text1.size();
    int n=text2.size();
    int dp[m+1][n+1];

        memset(dp,0,sizeof dp);
        //tabulation approach
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(text1[i-1]==text2[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[m][n];
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)