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

LeetCode 97 Interleaving String - Example and Complexity Analysis

Walkthrough and analysis

Trace s1 = "ab", s2 = "cd", s3 = "acbd".

Initialize: dp[0][0] = true.

First row (only s2): dp[0][1] = (s2[0]=='a'?) No, s2[0]='c' ≠ s3[0]='a'. False. First col (only s1): dp[1][0] = (s1[0]=='a'?) Yes. True. dp[2][0] = (s1[1]=='c'?) s1[1]='b' ≠ s3[1]='c'. False.

dp[1][1]: s3[1]='c'. From dp[0][1] (false). From dp[1][0] and s2[0]='c'='c'. True. dp[1][2]: s3[2]='b'. From dp[1][1] and s2[1]='d'≠'b'. From dp[0][2] (false). False. dp[2][1]: s3[2]='b'. From dp[1][1] and s1[1]='b'='b'. True. dp[2][2]: s3[3]='d'. From dp[2][1] and s2[1]='d'='d'. True.

Answer: true.

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