正文
【原创】leetCodeOj --- Interleaving String 解题报告
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
题目地址：
https://oj.leetcode.com/problems/interleaving-string/
题目内容：
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.
方法：
第一时间能想到的方法就是类似归并排序的思想。维护3个下标，分别指向s1、s2和s3。若s1[index1] == s3[index3]则 index1 ++ && index3 ++。反之若s2[index2] == s3[index3]则 index2 ++ && index3 ++。
但是这有个问题，就是如果s2[index2] == s1[index1]的话，选择谁呢？
答案是谁都选一次看看。于是，我们又要动态规划了。。
设dp[m][n] 为s1从下标m开始，s2从下标n开始是否能匹配下标从m + n开始的s3 （为什么是m + n？因为s1 m下标以前的字符和s2 n下标以前的字符都已经匹配过了）。如果值为1，那么可以匹配；如果为2，那么不能匹配。如果为0，那么需要递归调用子问题来解决。
简单看看动态规划方程：
dp[m][n] = {
s1[m] == s2[n] == s3[m+n] : dp[m][n+1] || dp[m+1][n]; // 若s1和s2当前都可以匹配，就都试一下，谁行谁就上。短路
s1[m] == s3[m+n] : dp[m+1][n]; // 仅当s1可以匹配
s2[n] == s3[m+n] : dp[m][n+1]; // 仅当s2可以匹配
else : false; // 谁都无法匹配
}
全部代码：
class Solution {
public:
string t1,t2,t3;
char dp[][]; // 没处理过就是0，处理了可以就是1，不行就是2
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size();
int len2 = s2.size();
int len3 = s3.size();
if (len1 + len2 != len3)
return false;
if (len1 == )
return s2 == s3 ? true : false;
if (len2 == )
return s1 == s3 ? true : false;
t1 = s1;
t2 = s2;
t3 = s3;
return trueStuff(,,len1,len2);
}
bool trueStuff(int m,int n,int len1,int len2) // m is index for s1,n is index for s2.
{
if (m >= len1 && n >= len2)
return true;
if (dp[m][n] != )
return dp[m][n] == ? true : false;
bool tmp = false; // mark if dp[m][n] can do the right thing.
if (m >= len1)
tmp = (t2[n] == t3[m+n] ? trueStuff(m,n + ,len1,len2) : false);
else if (n >= len2)
tmp = (t1[m] == t3[m+n] ? trueStuff(m + ,n,len1,len2) : false);
else if (t1[m] == t2[n] && t1[m] == t3[m+n])
tmp = (trueStuff(m + ,n,len1,len2) || trueStuff(m,n + ,len1,len2));
else if (t1[m] == t3[m+n])
tmp = trueStuff(m + ,n,len1,len2);
else if (t2[n] == t3[m+n])
tmp = trueStuff(m,n + ,len1,len2);
else
tmp = false;
dp[m][n] = (tmp == true ? : );
return tmp;
}
};
