Interlaving String
最后更新于：2022-04-01 22:57:09
**一. 题目描述**
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.
**二. 题目分析**
此题可使用二维动态规划来解决，下表给出了直观的匹配过程：
设某一格的状态为`k[i][j]`，表示`s1[i]`或`s2[j]`，与`s3[i+j]`的匹配结果。`s3`可与`s1`和`s2`相匹配时，可分为以下两种情况：
如果`s1` 的最后一个字符等于`s3` 的最后一个字符，则`k[i][j]=k[i-1][j]`；
如果`s2` 的最后一个字符等于`s3` 的最后一个字符，则`k[i][j]=k[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]);`
**三. 示例代码**
~~~
#include
#include
#include
using namespace std;
class Solution
{
public:
bool isInterleave(string s1, string s2, string s3)
{
if (s3.size() != s1.size() + s2.size())
return false;
if (s3[0] != s1[0] && s3[0] != s2[0])
return false;
vector > k(s1.size() + 1, vector(s2.size() + 1, false));
k[0][0] = true;
// 边界设置
for (size_t i = 1; i <= s1.size(); ++i)
k[i][0] = (s1[i - 1] == s3[i - 1]) && k[i - 1][0];
for (size_t j = 1; j <= s2.size(); ++j)
k[0][j] = (s2[j - 1] == s3[j - 1]) && k[0][j - 1];
for (size_t i = 1; i <= s1.size(); ++i)
{
for (size_t j = 1; j <= s2.size(); ++j)
{
k[i][j] = ((s1[i - 1] == s3[i + j - 1]) && k[i - 1][j]) ||
((s2[j - 1] == s3[i + j - 1]) && k[i][j - 1]);
}
}
return k[s1.size()][s2.size()];
}
};
~~~
**四. 小结**
编程时要注意边界条件的问题和数组的下标问题。
';