Interleave String

Problem:
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