Hints — p73 Interleaving String

Hint 1. Try greedy first (“take from whichever string matches s3’s next char”). Construct a counterexample where both s1 and s2 could provide the matching char but only one choice leads to success. Convince yourself greedy is wrong → you need DP.

Hint 2. Define dp[i][j] = True iff s3[:i+j] is an interleaving of s1[:i] and s2[:j]. The k-pointer for s3 is derived (k = i+j), not a free dimension.

Hint 3. Recurrence: dp[i][j] = (dp[i-1][j] AND s1[i-1]==s3[i+j-1]) OR (dp[i][j-1] AND s2[j-1]==s3[i+j-1]). Two terms = “last char came from s1” vs “last char came from s2”.

Hint 4. Precondition: len(s3) == len(s1) + len(s2) else immediate False. Initialize dp[0][0] = True. First row/column are purely-from-s2 / purely-from-s1 prefix matches.

Hint 5. Space optimization: rows depend only on previous row + left neighbor → 1D array of size min(m,n)+1. Swap s1/s2 so the inner loop is over the shorter dimension.

If stuck: see solution.py.