Code.txt

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

 

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.
Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.
Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.
 

Constraints:

1 <= text1.length, text2.length <= 1000
text1 and text2 consist of only lowercase English characters.


Solution 1 Top Down

class Solution {
public:
    int f(int i,int j,string &si,string &sj,vector<vector<int>> &dp)
    {
        if(i<0||j<0)
        {
            return 0;
        }
       else if(si[i]==sj[j])
       {
           return (1 + f(i-1,j-1,si,sj,dp));
       }
        else if(dp[i][j]!=-1)
        {
            return dp[i][j];
        }
        else
        {
            return dp[i][j] = max(f(i-1,j,si,sj,dp),f(i,j-1,si,sj,dp));
        }
    }
public:
    int longestCommonSubsequence(string text1, string text2) {
        int l1 = text1.length();
        int l2 = text2.length();
        vector<vector<int>> dp(l1,vector<int>(l2,-1));
        return f(l1-1,l2-1,text1,text2,dp);
    }
};




Solution 2 Bottom Up (with shifted coordinates  make changes in i and j for the string only,not int the dp and make size of dp l1+1*l2+1)
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
     int l1=text1.length();
     int l2=text2.length();
        vector<vector<int>> dp(l1+1,vector<int>(l2+1,0));
        for(int i=1;i<=l1;i++)
        {
            for(int j=1;j<=l2;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[l1][l2];
    }
};



Solution 3 : Space optimisation

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
     int l1=text1.length();
     int l2=text2.length();
        vector<int> curr(l2+1,0);
        vector<int> prev(l2+1,0);
        for(int i=1;i<=l1;i++)
        {
            for(int j=1;j<=l2;j++)
            {
                if(text1[i-1]==text2[j-1])
              {
                curr[j] = 1 + prev[j-1];
              }
               else
              {
                curr[j] = max(prev[j],curr[j-1]);
              }
            }
            prev=curr;
        }
        return prev[l2];
    }
};