Python Program to Find Longest Common Subsequence using Dynamic Programming with Memoization

This is a Python program to find longest common subsequence (LCS) of two strings using dynamic programming with top-down approach or memoization.

A string r is a subsequence of a string s if r can be obtained from s by dropping zero or more characters from s. A string r is a common subsequence of s and t if r is a subsequence of both s and t. A string r is a longest common subsequence (LCS) of s and t if there is no string that is longer than r and is a common subsequence of s and t. The problem is to find an LCS of two given strings.

1. Three functions are defined, lcs, lcs_helper and print_lcs.
2. lcs_helper takes as arguments two strings u, v; two indexes i, j; and a 2D table c.
3. c is a list of lists where c[i][j] will contain the length of an LCS of u[i:] and v[j:] where x[k:] is a substring of string x starting at index k.
4. The function returns the length of an LCS of u[i:] and v[j:] and fills in c as smaller subproblems for solving c[i][j] are solved.
5. The table c satisfies c[i][length of v] = 0 and c[length of u][j] = 0 for all i and j.
6. c also satisfies c[i][j] = 1 + c[i + 1][j + 1] if u[i] == v[j].
7. If u[i] != v[j], then c[i][j] = max(c[i + 1][j], c[i][j + 1]).
8. The function is implemented recursively and as the length of an LCS is found, it is stored in c.
9. If an LCS has already been calculated and stored in c, then it is immediately returned and not calculated again.
10. The function lcs takes two strings u and v as arguments.
11. It initializes a 2D table c as a list of lists and calls lcs_helper.
12. It returns the table c.
13. The function print_lcs takes as argument the two strings u, v and the table c as generated above.
14. It prints an LCS of u and v using the table c.

Here is the source code of a Python program to find an LCS of two strings using dynamic programming with memoization. The program output is shown below.

def lcs(u, v):
    """Return c where c[i][j] contains length of LCS of u[i:] and v[j:]."""
    c = [[-1]*(len(v) + 1) for _ in range(len(u) + 1)]
    lcs_helper(u, v, c, 0, 0)
    return c
 
 
def lcs_helper(u, v, c, i, j):
    """Return length of LCS of u[i:] and v[j:] and fill in table c.
 
    c[i][j] contains the length of LCS of u[i:] and v[j:].
    This function fills in c as smaller subproblems for solving c[i][j] are
    solved."""
    if c[i][j] >= 0:
        return c[i][j]
 
    if i == len(u) or j == len(v):
        q = 0
    else:
        if u[i] == v[j]:
            q = 1 + lcs_helper(u, v, c, i + 1, j + 1)
        else:
            q = max(lcs_helper(u, v, c, i + 1, j),
                    lcs_helper(u, v, c, i, j + 1))
    c[i][j] = q
    return q
 
 
def print_lcs(u, v, c):
    """Print one LCS of u and v using table c."""
    i = j = 0
    while not (i == len(u) or j == len(v)):
        if u[i] == v[j]:
            print(u[i], end='')
            i += 1
            j += 1
        elif c[i][j + 1] > c[i + 1][j]:
            j += 1
        else:
            i += 1
 
 
u = input('Enter first string: ')
v = input('Enter second string: ')
c = lcs(u, v)
print('Longest Common Subsequence: ', end='')
print_lcs(u, v, c)

1. The user is prompted to enter two strings.
2. lcs is called on the two strings to get the table c.
3. print_lcs is called to display an LCS of the two strings.

Case 1:
Enter first string: abcbdab
Enter second string: bdcaba
Longest Common Subsequence: bdab
 
Case 2:
Enter first string: director
Enter second string: secretary
Longest Common Subsequence: ectr
 
Case 3:
Enter first string: bisect
Enter second string: trisect
Longest Common Subsequence: isect

Sanfoundry Global Education & Learning Series – 1000 Python Programs.

If you wish to look at all Python Programming examples, go to 1000 Python Programs.