LintCode问题图解-21

本文准备讲解1个算法编程问题， 这个算法编程问题来自LintCode平台。不了解.LintCode平台的读者可以阅读笔者文章（在线编程平台推荐-LeetCode）。问题的英文版本描述如下：

Interleaving

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

Example

For s1 ="aabcc", s2 ="dbbca"

When s3 ="aadbbcbcac", return true.

When s3 ="aadbbbaccc", return false.

字符串

给出3个字符串:s1、s2、s3，判断s3是否由s1和s2生成。

样例

比如 s1 ="aabcc" s2 ="dbbca"

- 当 s3 ="aadbbcbcac"，返回  true.

- 当 s3 ="aadbbbaccc"， 返回 false.

这个问题的处理需要用到1种特殊的算法方案。这个算法方案需要用到1个计算矩阵。对应矩阵中的每个位置 [ i, j]，i 代表 s1 的长度，j 代表 s2 的长度; 位置 [ i, j] 的取值代表目标字符串对应字符串是否由s1和s2生成。计算矩阵的行数为  (s1 长度+1), 计算矩阵的列数为  (s2 长度+1)。位置 [ s1 长度, s2 长度] 取值即为问题输出结果。位置 [ 0, 0] 取值为 TRUE, 位置 [ 0, 1] 取值为 FALSE, 因为目标字符串的 a 和s2的 d 不同；目标字符串对应字符串不能由s1和s2生成。位置 [ 0, 2] 取值为 FALSE, 因为目标字符串的 aa 和s2的 db 不同；目标字符串对应字符串不能由s1和s2生成。位置 [ 1, 0] 取值为 TRUE, 因为目标字符串的 a 和s1的 a 相同；目标字符串对应字符串可以由s1和s2生成。位置 [ 2, 0] 取值为 TRUE, 因为目标字符串的 aa 和s1的 aa 相同；目标字符串对应字符串可以由s1和s2生成。计算矩阵的首行和首列计算完成后，所有位置取值都可以计算得出。目标字符串的字符来源只有3种可能：首个输入字符串，另1个输入字符串，其他的来源。

高效的算法