Lintcode29 Interleaving String solution problem solution

[topic description]

Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.

Three strings: S1, S2, S3 are given to determine whether S3 is composed of S1 and S2.

[topic link]

Http://www.lintcode.com/en/problem/interleaving-string/

[topic Analysis]

Dp [I] [j] denotes whether the first I of S1 and the first j of S2 are interleaving string or not.

Initialize first. Traverse S1, initializing all dp [I] [0]

Then iterate through S2 and initialize all dp [0] [j]

If the I + Jmur1 bit of S3 is equal to the I bit of S1, let's see if dp [I-1] [j] is true; isomorphic, and if the i+j-1 bit of S3 is equal to the j bit of S2, then let's see whether dp [I] [Jmur1] is true. As long as either of the two cases is true, dp [I] [j] is true.

[reference answer]

Http://www.jiuzhang.com/solutions/interleaving-string/