Thursday, April 25, 2013

Leetcode: Interleaving String in C++



Given s1s2s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbbaccc", return false.


When s3 = "aadbbcbcac", return true.
Solution: 

bool isInterleave(string s1, string s2, string s3) {
        int len1= s1.size();
        int len2 = s2.size();
        int len3 = s3.size();
        if(len1+len2!=len3)
        return false;
        vector<vector<bool> > match(len1+1, vector<bool>(len2+1,false));
        match[0][0] = true;
        for(int i = 0;i<len1;i++)
        {
            if(s1[i]==s3[i])
            match[i+1][0] = true;

            else
            break;

        }
        for(int i = 0;i<len2;i++)
        {
            if(s2[i]==s3[i])
            match[0][i+1] = true;
            else
            break;
        }
        for(int i = 1;i<=len1;i++)
        {
            char c1 = s1[i-1];
            for(int j = 1;j<=len2;j++)
            {
               char c2 = s2[j-1];
               char c3 = s3[i+j-1];
               if(c1==c3) // one situation is related to its previous one and current situation.
               match[i][j] = match[i-1][j]||match[i][j];
               if(c2==c3)
               match[i][j] = match[i][j-1]||match[i][j];
            }
        }
        return match[len1][len2];
    }

No comments:

Post a Comment