Medium 2D Table 2-D Dynamic Programming
In plain English: Find the longest sequence of characters that appears in both strings (not necessarily contiguous).
dp[i][j] = LCS of text1[:i] and text2[:j]. If chars match, dp[i][j] = dp[i-1][j-1] + 1. Otherwise, take max of skipping either character: max(dp[i-1][j], dp[i][j-1]).
Prompt
Given two strings text1 and text2, return the length of their longest common subsequence.
Try to write it from scratch before scrolling down.
Solution
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # chars match: extend the LCS by 1
else:
# skip one char from either string and keep the better result
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
# Test: longest_common_subsequence("abcde", "ace") == 3 ("ace")
# Test: longest_common_subsequence("abc", "def") == 0