Leetcode : 1143. Longest Common Subsequence (DP)

tags:leetcode

Memoization methods

class Solution {
public:    
    int dp[1000 + 1][1000 + 1];
    
    int maxLen(string& s1, string& s2, int n, int m)
    {
        if (n == 0 || m == 0)
            return 0;
        
        if (dp[n][m] != -1)
            return dp[n][m];

        if (s1[n - 1] == s2[m - 1])
            return dp[n][m] = 1 + maxLen(s1, s2, n - 1, m - 1);
        else
            return dp[n][m] = max(maxLen(s1, s2, n - 0, m - 1), maxLen(s1, s2, n - 1, m - 0));
    }
        
    int longestCommonSubsequence(string s1, string s2) 
    {
        memset(dp, -1, sizeof(dp));        
        return maxLen(s1, s2, s1.length(), s2.length());
    }
};

Tabulation methods

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size(),n=text2.size();
        int dp[m+1][n+1];
        // set default value
        for(int i=0;i<m+1;i++){
            dp[i][0]=0;
        }
        for(int i=0;i<n+1;i++){
            dp[0][i]=0;
        }
        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
               if(text1[i-1]==text2[j-1]){
                  dp[i][j]= 1+dp[i-1][j-1]; // char string1 equal string2 , count + 1 
               }else{
                   dp[i][j]=max(dp[i-1][j],dp[i][j-1]); //now is before max count.
               } 
            }
        }
        return dp[m][n];
    }
};

//Tabulation methods
//rule condtion
//run all 2d array
//1. find word , move text1 , move text2
//2. not find , now set copy max before
//3. return last array is answer