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.
设状态f[i][j]，表示s1[0,i]和s2[0,j]，匹配s3[0, i+j]。如果s1的最后一个字符等于s3的最后一个字符，则f[i][j]=f[i-1][j]；如果s2的最后一个字符等于s3的最后一个字符，则f[i][j]=f[i][j-1]。因此状态转移方程如下：
f[i][j] = (s1[i - 1] == s3 [i + j - 1] && f[i - 1][j])
|| (s2[j - 1] == s3 [i + j - 1] && f[i][j - 1]);
{% codesnippet "./code/interleaving-string-1."+book.suffix, language=book.suffix %}{% endcodesnippet %}
{% codesnippet "./code/interleaving-string-2."+book.suffix, language=book.suffix %}{% endcodesnippet %}
{% codesnippet "./code/interleaving-string-3."+book.suffix, language=book.suffix %}{% endcodesnippet %}