LeetCode Q97: Interleaving String (hard)

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.

Solution. 

Question should be solved using DP.

Idea is to consider whether  the first (i+j) substring of s3 is a interleaving of s1(0:i) and s2(0:j).

To decide (i, j) entry of a tracking table, we should look at two entries (i-1, j) and (i, j-1). Because, if (i, j) is an interleaving of s1(0:i) and s2(0:j). Then it must be one of following two cases:

Case 1. if Table(i-1, j) is an interleaving. Then Table(i, j) is an interleaving too when s1(i-1) == s3(i+j-1). Because the character s(i-1) must be added to the tail of s3(0:i+j-2) to become to s2(0:i+j-1) .

Case 2. if Table(i, j-1) is an interleaving. Then Table (i, j) is an interleaving too when s2(j-1) == s3(i+j-1). The reason is as similar as Case 1.

So, Table(i, j) will be true when any of above cases is true. Otherwise Table(i, j) is a false.