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]: ifs1[i-1] == s3[i+j-1], we can extend. - From
dp[i][j-1]: ifs2[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].