4 Solutions, Building from Recursive to Space Optimized LCS


#1

Recursive Solution
Here the base case occurs when any of the string lengths under consideration reduces to 0. Coming to recursive cases, if the character at mth position of s1 is the same as that of the nth part of s2, then add 1 to the length of result and call LCS with both sizes reduced by 1. Else, Check 2 cases by individually reducing m and n by one and get the maximum out of them.

// m and n are string lengths of s1 and s2 respectively
int Solution::lcs(string s1, string s2, int m, int n) 
{
    // Base Case: If any of string lengths reaches 0, then return lcs as 0
    if(m == 0 or n == 0)
    {
        return 0;
    }
    
    // If m th character of s1 and n th character of s2 is same
    if(s1[m - 1] == s2[n - 1])
    {
        // Then add one to length of lcs, and reduce both string lengths by 1
        return 1 + lcs(s1, s2, m - 1, n - 1)
    }
    
    else
    {
        // Else check 2 cases, reducing strings lengths one at a time for each of strings
        // And whichever, returns max of them, is lcs of this m and n
        max(lcs(s1, s2, m - 1, n), lcs(s1, s2, m, n - 1));
    }
}

Time Complexity = O(2 ^ n)

Memoization
In the Recursive solution, many of the subproblems are overlapping. To prevent recomputation of subproblems, we can use a 2D array of size (m + 1) x (n + 1) for storing the result. A 2D array is used since we have two changing parameters ‘m’ and ‘n’.

// Assume that memo has all values initialized to -1(Not computed) initially
int memo[m + 1][n + 1];

// m and n are string lengths of s1 and s2 respectively
int Solution::lcs(string s1, string s2, int m, int n) 
{
    // Check if result is already computed for m and n
    if(memo[m][n] != -1)
    {
        return memo[m][n];
    }
    
    // Base Case: If any of string lengths reaches 0, then return lcs as 0
    if(m == 0 or n == 0)
    {
        memo[m][n] = 0;
    }
    
    // If m th character of s1 and n th character of s2 is same
    else if(s1[m - 1] == s2[n - 1])
    {
        // Then add one to length of lcs, and reduce both string lengths by 1
        memo[m][n] = 1 + lcs(s1, s2, m - 1, n - 1)
    }
    
    else
    {
        // Else check 2 cases, reducing strings lengths one at a time for each of strings
        // And whichever, returns max of them, is lcs of this m and n
        memo[m][n] = max(lcs(s1, s2, m - 1, n), lcs(s1, s2, m, n - 1));
    }
    return memo[m][n];
}

Time Complexity = Theta(m *n)
Space Complexity = Theta(m * n) + Recursion depth overhead

Tabulation

int Solution :: solve(string s1, string s2)
{
    // your code here
    int m = s1.size(), n = s2.size();
    int dp[m + 1][n + 1];
    
    // Firstly set first row and first column as 0, as they denote 0 length for both strings
    for(int i = 0; i <= n; i++)
    {
        dp[0][i] = 0;
    }
    
    for(int j = 0; j <= m; j++)
    {
        dp[j][0] = 0;
    }
    
    // Start from length 1 for each row
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            // Same 2 cases as previous solutions
            if(s1[i - 1] == s2[j - 1])
            {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            }
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    // Solution is at dp[m][n]
    return dp[m][n];
}

Time Complexity = Theta(m *n)
Space Complexity = Theta(m * n) but avoids recursion overhead.

Space Optimized Tabulation
One critical observation which can improve our space complexity is that dp[i][j] can either be
dp[i][j] = 1 + dp[i - 1][j - 1] or dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]). So having the current row and previous row should suffice, as they can be overwritten for further iterations.

int Solution :: solve(string s1, string s2)
{
    int m = s1.size(), n = s2.size();
    int dp[2][n + 1];
    bool bi;
    for(int j = 0; j <= n; j++)
    {
        dp[0][j] = 0;
    }
    dp[1][0] = 0;
    
    for(int i = 1; i <= m; i++)
    {
        bi = i & 1; // Check if even or odd
        for(int j = 1; j <= n; j++)
        {
            if(s1[i - 1] == s2[j - 1])
            {
                dp[bi][j] = dp[1 - bi][j - 1] + 1;
            }
            else
            {
                dp[bi][j] = max(dp[1 - bi][j], dp[bi][j - 1]);
            }
        }
    }
    return dp[bi][n];   
}

Time Complexity = Theta(m *n)
Space Complexity = Theta(n)


#2

Thanks for compiling different approaches man!!


#3

correction: space complexity = theta( min(m,n));
swap s1 and s2 beforehand if n < m;