THE PROBLEM
Subsequence, not substring
Given two strings, return the length of their longest common subsequence. For example, given text1 = "abcde" and text2 = "ace", the longest common subsequence is "ace", which has a length of 3. A substring and a subsequence are different: a substring is contiguous, while a subsequence only needs to preserve the relative order of its characters.
DP INITIALIZATION
Add an empty row and column
For strings with lengths m and n, initialize dp with m + 1 rows and n + 1 columns. The extra row and column represent an empty prefix. Every cell along those edges starts at 0, because the longest common subsequence between an empty string and any other string has length zero.
dp = [[0] * (n + 1) for _ in range(m + 1)]THE 2D TABLE
Follow the nested loops
Rows represent prefixes of text1 = "abcde"; columns represent prefixes of text2 = "ace". Focus any cell to see what the loop has already visited and which neighboring values determine the current result.
a matches a: take diagonal 0 + 1 = 1.
Hover over a cell or use Tab to follow the nested loops from left to right, then top to bottom.
If the characters match, extend the diagonal: dp[i][j] = 1 + dp[i-1][j-1]. Otherwise, keep the better of the top and left cells.PYTHON
Translate the recurrence directly
class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: rows, cols = len(text1) + 1, len(text2) + 1 dp = [[0] * cols for _ in range(rows)] for i in range(1, rows): for j in range(1, cols): if text1[i - 1] == text2[j - 1]: dp[i][j] = 1 + dp[i - 1][j - 1] else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[-1][-1]COMPLEXITY
One state for every pair of prefixes
For strings of lengths m and n, the table contains (m + 1)(n + 1) cells. Each takes constant work, giving O(mn) time and O(mn) space. Space can be reduced to O(n) by retaining only the previous row.