Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Problem

Longest Common Subsequence

LeetCode #1143Medium

Grid DP · match → diagonal+1, else max(up, left)

Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence keeps relative order but need not be contiguous. If there is no common subsequence, return 0.

Asked atAmazonGoogleMicrosoft

2-D tabulation

time O(m·n)space O(m·n)

step 1 / 18

dp · rows = "abcde", cols = "ace" · dp[i][j] = LCS(s1[:i], s2[:j])

2-D tabulation


▸
1dp = (m+1) × (n+1) grid of 0   // row 0 / col 0 = empty prefix
2for i in 1..m: for j in 1..n:
3    if s1[i−1] == s2[j−1]:
4        // match → extend diagonal
5        dp[i][j] = dp[i−1][j−1] + 1
6    else:
7        dp[i][j] = max(dp[i−1][j], dp[i][j−1])
8 
9return dp[m][n]

state

s1 (rows)abcde
s2 (cols)ace
statedp[i][j] = LCS(s1[:i], s2[:j])

line 1Find the longest common subsequence of s1 = "abcde" and s2 = "ace". Define dp[i][j] = length of the LCS of the first i chars of s1 and the first j chars of s2. s1 runs DOWN the rows, s2 runs ACROSS the columns. The answer sits at the bottom-right.