LeetCode 97 Interleaving String - Solution

Define dp[i][j] = true if first i characters of s1 and first j characters of s2 can interleave to form first i+j characters of s3.

Transitions:

• From dp[i-1][j]: if s1[i-1] == s3[i+j-1], we can extend.
• From dp[i][j-1]: if s2[j-1] == s3[i+j-1], we can extend.

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]).

Base: dp[0][0] = true. Answer: dp[m][n].