Longest Common Subsequence

LeetCode 1143 • Medium • Dynamic Programming

Return the length of the longest common subsequence of text1 and text2. Example: "ace" vs "abcde" → 3 ("ace").

TimeO(m×n)

SpaceO(m×n)

dp[i][j]: —

Current cell

Result

dp[i][j]—

Speed:

Ready

Press Play. If chars match: extend LCS by 1. Else: take the better of skipping left or top.

Whiteboard

Size:3

Type It

Practice until you don't need to look. Match → +1 from diagonal. Else max(up, left).

═══ LCS — 2D DP ═══

PATTERN ▸ Longest common subsequence O(mn)

① BASE

dp[i][0]=0, dp[0][j]=0

② FOR i,j

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

return dp[m][n]

your implementation

Verify: