Summary - LCS

Print the LCS length for two strings in a mini task.

Summary - LCS

LCS finds the longest common subsequence of two sequences with a 2D DP table and backtracking. It is used in DNA alignment and diff tools.

In this mini task you will print the LCS length of two strings; combine all steps.

LCS gives Θ(mn) time and memory; it is a classic DP problem.

Exercise Print LCS

Write lcs_print(s1, s2). Print the LCS length with print(). Output of lcs_print("AGGTAB", "GXTXAYB"): 4.

Show example solution

def lcs_print(s1, s2):
    # Print LCS
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    print(dp[m][n])
lcs_print("AGGTAB", "GXTXAYB")

Test yourself

Summary - LCS: match the terms

LCS

Common subseq
DP

Table
backtrack

Backtrack
O(mn)

Bilinear

Table size

dp = [[0] * (n + 1) for _ in range(____ + 1)

Show answer

dp = [[0] * (n + 1) for _ in range(m + 1)

What is LCS's time complexity?
- O(mn)
- O(n^2)
- O(m^2)
- O(m + n)
Show answer

O(mn) — O(mn).

Next lesson: Knapsack problem

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies