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 – Python Programs.**

To practice all Python programs, __here is complete set of 150+ Python Problems and Solutions__.

**If you find any mistake above, kindly email to [email protected]**

**Related Posts:**

- Apply for Programming Internship
- Practice Programming MCQs
- Check Information Technology Books
- Check Python Books
- Apply for Python Internship