[Leetcode] Interleaving String

Problem 

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For example,
Given: s1 = "aabcc", s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

Algorithm

For each character in s3, we need to locate it either in s1 or s2. 

Let dp[i][j] indicates whether s3.substring(0,i+j) can be found in s1.substring(0,i) and s2.substring(0,j). The recurrence is shown in the code. 

Code