Interleaving String

Given strings s1, s2, and s3, return whether s3 can be formed by interleaving s1 and s2.
An interleaving uses every character from both source strings exactly once while preserving the left-to-right order within each source. Characters chosen from the two sources may alternate in groups of any positive length.

Function
isInterleave(s1: String, s2: String, s3: String) → boolean

Examples
Example 1
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbcbcac"
return = true
The target can choose characters from both source strings while retaining each source's internal order.
Example 2
s1 = "aabcc"
s2 = "dbbca"
s3 = "aadbbbaccc"
return = false
Every possible choice eventually needs to reverse or skip a character from one source, so the target is not an interleaving.
Example 3
s1 = ""
s2 = ""
s3 = ""
return = true
The empty target uses every character from both empty source strings.

Constraints
0 <= s1.length, s2.length <= 100.
0 <= s3.length <= 200.
All three strings contain only lowercase English letters.

First check: if len(s1) + len(s2) != len(s3), return false immediately. Then define dp[i][j] as true if the first i chars of s1 and first j chars of s2 can interleave into the first i+j chars of s3. dp[0][0] is true. Fill each cell from two sources: dp[i-1][j] is true and s1[i-1] equals s3[i+j-1], or dp[i][j-1] is true and s2[j-1] equals s3[i+j-1]. The answer is dp[m][n]. That's O(m*n) time, about 10,000 cells, trivial. The common pitfall is greedy matching: when both s1 and s2 match the current s3 char, picking one can be wrong, so you need DP or memoized recursion. Another miss is forgetting the first row and column, where one string is empty. You can compress to a single row of size n+1. If you freeze on the recurrence during the live OA, StealthCoder can hand you the working table as a hedge.

If you see this problem in your OA tomorrow, the play is to recognize the pattern in 30 seconds. StealthCoder buys you that recognition.