Dynamic Programming/Practice/Longest Common Subsequence
Longest Common Subsequence - DP Table Explained
Fill a grid where row i, column j answers: how long is the LCS of the first i letters of one string and the first j of the other? Letters match: take the diagonal plus one. They differ: take the better of the cell above or to the left.
Why it works
The grid memoizes every prefix pair, so no comparison is ever repeated. Each cell reads only neighbours, giving O(m·n) time and space - and the space drops to two rows because a cell never needs anything further back than the previous row.
The problem
Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is a sequence derived by deleting some characters without changing the relative order.
Hints
- dp[i][j] = LCS of text1[:i] and text2[:j].
- If text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
- Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- Build the table iterating both strings.
Test cases
| Input | Expected |
|---|---|
lcs("abcde", "ace") | 3 |
lcs("abc", "abc") | 3 |
lcs("abc", "def") | 0 |
Reference starter code
def lcs(text1, text2):
# 2D DP table
pass
print(lcs("abcde", "ace")) # 3 ("ace")
print(lcs("abc", "abc")) # 3 ("abc")
print(lcs("abc", "def")) # 0
More challenges in this topic
Try it yourself
Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.