# leetcode: Interleaving String

#### Problem Description:

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 and Precautions:

This is dp problem:

Let F(i, j) denote if s1 of length i and s2 of length j could form s3 of lenght i+j, then we have four cases:
(1) F(i, j) = F(i-1, j)                              if s1[i-1] == s3[i+j-1] && s2[j-1] != s3[i +j -1]
(2) F(i, j) = F(i, j-1)                              if s1[i-1] != s3[i+j-1]  && s2[j-1] == s3[i +j -1]
(3) F(i, j) = F(i-1, j) || F(i, j-1)             if s1[i-1] == s3[i+j-1] && s2[j-1] == s3[i +j -1]
(4) F(i, j) = false                                   if s1[i-1] != s3[i+j-1] && s2[j-1] != s3[i +j -1]

#### Tips and Divergent thinking:

N/A

（全文完，原创文章，转载时请注明作者和出处）

（转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com，请勿用于任何商业用途）

Written on June 5, 2013