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.
Recursive Solution :
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size3 = s3.size(), size1 = s1.size(), size2 = s2.size();
if (size3 != size1 + size2)
return false;
else if (size1 < 2 && size2 < 2) {
if (s3 == s1 + s2 || s3 == s2 + s1)
return true;
else
return false;
} else if (size1 >= 2 && size2 == 0) {
return (s3 == s1);
} else if (size2 >= 2 && size1 == 0) {
return (s3 == s2);
} else {
if (s3[0] == s1[0] && s3[0] == s2[0]) {
string copy_s3 = s3;
string copy_s1 = s1;
return isInterleave(s1.erase(0,1), s2, s3.erase(0,1)) ||
isInterleave(copy_s1, s2.erase(0, 1), copy_s3.erase(0,1));
} else if (s3[0] == s1[0])
return isInterleave(s1.erase(0,1), s2, s3.erase(0,1));
else if (s3[0] == s2[0])
return isInterleave(s1, s2.erase(0, 1), s3.erase(0,1));
else
return false;
}
}
};
No comments:
Post a Comment