Pattern 22: LeetCode Interview Patterns24 sections · 736 units
Open in Course

LeetCode 1143 Longest Common Subsequence - Example and Complexity Analysis

Walkthrough and analysis

Trace text1 = "abc", text2 = "ac".

Initialize row 0 and col 0 to 0.

i=1 (text1[0]='a'): j=1 (text2[0]='a'): Match! dp[1][1] = dp[0][0] + 1 = 1. j=2 (text2[1]='c'): No match. dp[1][2] = max(dp[0][2], dp[1][1]) = max(0, 1) = 1.

i=2 (text1[1]='b'): j=1: No match. dp[2][1] = max(dp[1][1], dp[2][0]) = max(1, 0) = 1. j=2: No match. dp[2][2] = max(dp[1][2], dp[2][1]) = max(1, 1) = 1.

i=3 (text1[2]='c'): j=1: No match. dp[3][1] = 1. j=2: Match! dp[3][2] = dp[2][1] + 1 = 2.

Answer: 22. LCS is "ac".

O(m×n)O(m \times n) time and space.