题目描述：
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.
bool isInterleave(string s1, string s2, string s3) {
if(s3.size() != s1.size() + s2.size()){
return false;
}
return isInterleave(begin(s1),end(s1),begin(s2),end(s2),begin(s3),end(s3));
}
template<typename Iter>
bool isInterleave(Iter first1,Iter last1,Iter first2,Iter last2,Iter first3,Iter last3){
if(first3 == last3){
return first1 == last1 && first2 == last2;
}
return (*first1 == *first3 && isInterleave(next(first1),last1,first2,last2,next(first3),last3 )) || ( *first2 == *first3 && isInterleave(first1,last1,next(first2),last2,next(first3),last3));
}
最直观的解法就是这样，但是会超时。
bool isInterleave(string s1, string s2, string s3) {
vector<vector<bool>> f(s1.size() + 1,vector<bool>(s2.size() + 1,true));
if(s1.size() + s2.size() != s3.size()){
return false;
}
for(int i = 1;i <= s1.size();i++){
f[i][0] = f[i - 1][0] && s1[i - 1] == s3[i - 1];
}
for(int j = 1;j <= s2.size();j++){
f[0][j] = f[0][j - 1] && s2[j - 1] == s3[j - 1];
}
for(int i = 1;i <= s1.size();i++){
for(int j = 1;j <= s2.size();j++){
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]);
}
}
return f[s1.size()][s2.size()];
}