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.
思想： 动态规划。
DP[i][j] = (DP[i-1][j] && s1[i-1] == s3[i+j-1]) || (DP[i][j-1] && s2[j-1] == s3[i+j-1]); 其中，i, j 分别为字符串 s1, s2 的当前长度。
方法一：
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s1.size() + s2.size() != s3.size()) return false;
if(s1 == "") return s2 == s3;
if(s2 == "") return s1 == s3;
vector<vector<bool> > DP(s1.size()+1, vector<bool>(s2.size()+1, false));
DP[0][0] = true;
for(size_t i = 1; i <= s1.size(); ++i) {
DP[i][0] = (DP[i-1][0] && s1[i-1] == s3[i-1]);
for(size_t j = 1; j <= s2.size(); ++j) {
DP[0][j] = (DP[0][j-1] && s2[j-1] == s3[j-1]);
DP[i][j] = (DP[i-1][j] && s1[i-1] == s3[i+j-1]) || (DP[i][j-1] && s2[j-1] == s3[i+j-1]);
}
}
return DP[s1.size()][s2.size()];
}
};
方法二： 进一步优化，空间复杂度， O(min(s1.size(), s2.size()));
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s1.length() + s2.length() != s3.length()) return false;
if(s1 == "") return s2 == s3;
if(s2 == "") return s1 == s3;
if(s2.size() > s1.size()) s1.swap(s2); // make the sapce O(min(s1.size(), s2.size()));
vector<bool> DP(s2.size()+1);
for(size_t i = 0; i <= s1.size(); ++i) {
DP[0] = (!i || (DP[0] && s1[i-1] == s3[i-1]));
for(size_t j = 1; j <= s2.size(); ++j) {
DP[j] = (DP[j] && s1[i-1] == s3[i+j-1]) || (DP[j-1] && s2[j-1] == s3[i+j-1]);
}
}
return DP[s2.size()];
}
};
原文：http://www.cnblogs.com/liyangguang1988/p/3940158.html