Summary - LCS
- Algorithms course
- Advanced
- Lesson 12/56
- 4 min
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.
Practice Print LCS
Write lcs_print(s1, s2). Print the LCS length with print(). Output of lcs_print("AGGTAB", "GXTXAYB"): 4.
Starter code
def lcs_print(s1, s2):
# Print LCSSample 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")Expected output
4
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Summary - LCS: match the terms
| Term | Meaning |
|---|---|
LCS |
Common subseq |
DP |
Table |
backtrack |
Backtrack |
O(mn) |
Bilinear |
2 Table size
Question
dp = [[0] * (n + 1) for _ in range(____ + 1)
Answer
dp = [[0] * (n + 1) for _ in range(m + 1)Explanation: m is right.
3 What is LCS's time complexity?
- O(mn) Correct answer
- O(n^2)
- O(m^2)
- O(m + n)
Explanation: O(mn).