Doubt in lcs implementation?

#1

time complexity will be 0(n^2) right?
and bottom-up app is not discussed? and how to print the lcs is also not there ?

#2

O(n*m) where n is length of 1st string and m is length of 2nd string

I am not sue if its present later in the lectures or not please check urself
Otherwise refer to this in case its not present

  1. Construct dp[m+1][n+1] using the count LCS dynamic programming solution.
  2. The value dp[m][n] contains length of LCS. Create a character array lcs[] of length equal to the length of lcs plus 1 (one extra to store \0).
  3. Traverse the 2D array starting from dp[m][n]. Do following for every cell dp[i][j]
  • If characters (in X and Y) corresponding to dp[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.
  • Else compare values of dp[i-1][j] and dp[i][j-1] and go in direction of greater value.
string lcs(string a,string b)
{
    int la=a.length();
    int lb=b.length();
    int dp[1001][1001] = {0};

    for(int i=0;i<=la;i++)
    {
        dp[i][0]=0;
    }
    for(int i=0;i<=lb;i++)
    {
        dp[0][i]=0;
    }

    // Following steps build dp[m+1][n+1] in bottom up fashion. Note 
    // that dp[i][j] contains length of LCS of a[0..i-1] and b[0..j-1]
    for(int i=1;i<=la;i++)
    {
        for(int j=1;j<=lb;j++)
        {
            if(a[i-1]==b[j-1])
            {
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else
            {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    int i=la,j=lb;
    string ans="";
    // Start from the right-most-bottom-most corner and 
    // one by one store characters in lcs[] 
    while(i>0 && j>0)
    {
        if(a[i-1] == b[j-1])
        {
            // If current character in a and b are same, then 
            // current character is part of LCS 
            ans=a[i-1]+ans;
            i--;
            j--;
        }
        // If not same, then find the larger of two and 
        // go in the direction of larger value
        else if(dp[i-1][j]>dp[i][j-1])
        {
            i--;
        }
        else
        {
            j--;
        }
    }

    return ans;
}
#3

sir why is the 2d vector in the video is send by reference in the lcs function?

#4

Why 2d vector ? because 2 strings and hence 2 states so 2d matrix
Why by reference ? If its not passed by reference then how its beneficial to save the result
the main objective of memoisation is to not calculate again if we already have answers saved corresponding to it

#5

but we are in the same function lcs …then what is the need of sending it by reference ?

#6

We are in same function but difeerent subcalls of lcs
Now any change done in subcall will not be reflected in vector unless its passed by reference

#7

okay !! this is due to recursion right ?

#8

Yeah …