Given two strings text1 and text2, return the length of their longest common subsequence, the longest string that is a subsequence of both. A subsequence deletes some characters (possibly none) without changing the order of the rest. Return 0 if they share no characters.
- 1 <= text1.length, text2.length <= 1000
- Both strings are lowercase English letters
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Listing all 2^n subsequences of one string and checking each in the other is hopeless. State: dp[i][j] = LCS length of text1[0..i) and text2[0..j). Recurrence: if text1[i-1] == text2[j-1], that character extends the LCS of the shorter prefixes, so dp[i][j] = dp[i-1][j-1] + 1; otherwise drop the last character of one string: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base case: an empty prefix gives 0, so row 0 and column 0 are 0. The memoised recursion lcs(i, j) has m * n states; the table fills them row by row without recursion.
Algorithm
- Create a
(m + 1) x (n + 1)table of zeros. - For
ifrom 1 tomandjfrom 1 ton: - If the characters
text1[i-1]andtext2[j-1]match, setdp[i][j] = dp[i-1][j-1] + 1. - Otherwise set
dp[i][j] = max(dp[i-1][j], dp[i][j-1]). - Return
dp[m][n].
O(m * n)Space: O(m * n), reducible to O(min(m, n))dp[m][n], which needs the full table.class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] # empty prefix -> 0 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 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[m][n]