Longest Common Subsequence (LCS) using Memoization

Longest Common Subsequence (LCS) using Recursion:

Longest Common Subsequence (LCS) using Bottom-Up (Tabulation):

If we notice carefully, we can observe that the above recursive solution holds the following two properties:

1. Optimal Substructure:

See for solving the structure of L(X[0, 1, . . ., m-1], Y[0, 1, . . . , n-1]) we are taking the help of the substructures of X[0, 1, …, m-2], Y[0, 1,…, n-2], depending on the situation (i.e., using them optimally) to find the solution of the whole.

2. Overlapping Subproblems:

If we use the above recursive approach for strings “BD” and “ABCD“, we will get a partial recursion tree as shown below. Here we can see that the subproblem L(“BD”, “ABCD”) is being calculated more than once. If the total tree is considered there will be several such overlapping subproblems.

L(“AXYT”, “AYZX”)
/ \
L(“AXY”, “AYZX”) L(“AXYT”, “AYZ”)
/ \ / \
L(“AX”, “AYZX”) L(“AXY”, “AYZ”) L(“AXY”, “AYZ”) L(“AXYT”, “AY”)

Approach: Because of the presence of these two properties we can use Dynamic programming or Memoization to solve the problem. Below is the approach for the solution using recursion.

Create a recursive function. Also create a 2D array to store the result of a unique state.
During the recursion call, if the same state is called more than once, then we can directly return the answer stored for that state instead of calculating again.

Below is the implementation of the above approach:

C++

// A Top-Down DP implementation
// of LCS problem
#include <bits/stdc++.h>
using namespace std;

// Returns length of LCS for X[0..m-1],
// Y[0..n-1]
int lcs(char* X, char* Y, int m, int n,
        vector<vector<int> >& dp)
{
    if (m == 0 || n == 0)
        return 0;
    if (X[m - 1] == Y[n - 1])
        return dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);

    if (dp[m][n] != -1) {
        return dp[m][n];
    }
    return dp[m][n] = max(lcs(X, Y, m, n - 1, dp),
                          lcs(X, Y, m - 1, n, dp));
}

// Driver code
int main()
{
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";

    int m = strlen(X);
    int n = strlen(Y);
    vector<vector<int> > dp(m + 1, vector<int>(n + 1, -1));
    cout << "Length of LCS is " << lcs(X, Y, m, n, dp);

    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;

class GFG {

    // A Top-Down DP implementation of LCS problem

    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    static int lcs(String X, String Y, int m, int n,
                   int[][] dp)
    {

        if (m == 0 || n == 0)
            return 0;

        if (dp[m][n] != -1)
            return dp[m][n];

        if (X.charAt(m - 1) == Y.charAt(n - 1)) {
            dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);
            return dp[m][n];
        }

        dp[m][n] = Math.max(lcs(X, Y, m, n - 1, dp),
                            lcs(X, Y, m - 1, n, dp));
        return dp[m][n];
    }

    // Drivers code
    public static void main(String args[])
    {

        String X = "AGGTAB";
        String Y = "GXTXAYB";

        int m = X.length();
        int n = Y.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m + 1; i++) {
            for (int j = 0; j < n + 1; j++) {
                dp[i][j] = -1;
            }
        }

        System.out.println("Length of LCS is "
                           + lcs(X, Y, m, n, dp));
    }
}

// This code is contributed by shinjanpatra

Python

# A Top-Down DP implementation of LCS problem

# Returns length of LCS for X[0..m-1], Y[0..n-1]


def lcs(X, Y, m, n, dp):

    if (m == 0 or n == 0):
        return 0

    if (dp[m][n] != -1):
        return dp[m][n]

    if X[m - 1] == Y[n - 1]:
        dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp)
        return dp[m][n]

    dp[m][n] = max(lcs(X, Y, m, n - 1, dp), lcs(X, Y, m - 1, n, dp))
    return dp[m][n]

# Driver code


X = "AGGTAB"
Y = "GXTXAYB"

m = len(X)
n = len(Y)
dp = [[-1 for i in range(n + 1)]for j in range(m + 1)]

print(f"Length of LCS is {lcs(X, Y, m, n, dp)}")

# This code is contributed by shinjanpatra

/* C# Naive recursive implementation of LCS problem */
using System;

class GFG {

    /* Returns length of LCS for X[0..m-1], Y[0..n-1] */
    static int lcs(char[] X, char[] Y, int m, int n,
                   int[, ] L)
    {
        if (m == 0 || n == 0)
            return 0;

        if (L[m, n] != -1)
            return L[m, n];

        if (X[m - 1] == Y[n - 1]) {
            L[m, n] = 1 + lcs(X, Y, m - 1, n - 1, L);
            return L[m, n];
        }

        L[m, n] = max(lcs(X, Y, m, n - 1, L),
                      lcs(X, Y, m - 1, n, L));
        return L[m, n];
    }

    /* Utility function to get max of 2 integers */
    static int max(int a, int b) { return (a > b) ? a : b; }

    public static void Main()
    {
        String s1 = "AGGTAB";
        String s2 = "GXTXAYB";

        char[] X = s1.ToCharArray();
        char[] Y = s2.ToCharArray();
        int m = X.Length;
        int n = Y.Length;
        int[, ] L = new int[m + 1, n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                L[i, j] = -1;
            }
        }
        Console.Write("Length of LCS is"
                      + " " + lcs(X, Y, m, n, L));
    }
}

// This code is contributed by akshitsaxenaa09

Javascript

/* A Top-Down DP implementation of LCS problem */

/* Returns length of LCS for X[0..m-1], Y[0..n-1] */
function lcs(X, Y, m, n, dp)
{
    if (m == 0 || n == 0)
        return 0;
    if (X[m - 1] == Y[n - 1])
        return dp[m][n] = 1 + lcs(X, Y, m - 1, n - 1, dp);

    if (dp[m][n] != -1) {
        return dp[m][n];
    }
    return dp[m][n] = Math.max(lcs(X, Y, m, n - 1, dp),
                          lcs(X, Y, m - 1, n, dp));
}

/* Driver code */

let X = "AGGTAB";
let Y = "GXTXAYB";

let m = X.length;
let n = Y.length;
let dp = new Array(m + 1);
for(let i = 0; i < m + 1; i++)
{
    dp[i] = new Array(n + 1).fill(-1);
} 
console.log("Length of LCS is " + lcs(X, Y, m, n, dp));

// This code is contributed by shinjanpatra

Output

Length of LCS is 4

Time Complexity: O(m * n) where m and n are the string lengths.
Auxiliary Space: O(m * n) Here the recursive stack space is ignored.