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.
*/

class Solution {
public:

    void helper(string& s1, int p1, string& s2, int p2, string& s3, int p3, bool& res)
    {
        if (p3 == -1 || res)
        {
            res = true;
            return;
        }
        
        if (s3[p3] != s1[p1] && s3[p3] != s2[p2]) return;
      
        if (s3[p3] == s2[p2] && s3[p3] == s1[p1])
        {
            helper(s1, p1, s2, p2 - 1, s3, p3 - 1, res);
            helper(s1, p1 - 1, s2, p2, s3, p3 - 1, res);
        }
        if (s3[p3] == s2[p2])
        {
            helper(s1, p1, s2, p2 - 1, s3, p3 - 1, res);
        }
        else
        {
            helper(s1, p1 - 1, s2, p2, s3, p3 - 1, res);
        }
    }

    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function 
        if (s1.empty() && s2.empty() && s3.empty()) return true;
        
        unordered_map<char, int> check;
        
        if (s3.size() != s1.size() + s2.size()) return false;
        
        bool res = false;
        helper(s1, s1.size() - 1, s2, s2.size() - 1, s3, s3.size() - 1, res);
        return res;
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s