Monday, November 25, 2013

LeetCode Problem : Interleaving String

Problem 


Given s1s2s3, 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.

Code

bool isInterleave(string s1, string s2, string s3) {
// Start typing your C/C++ solution below
// DO NOT write int main() function    
    int m = s1.size();
    int n = s2.size();
    if(s3.size() != m + n)
    return false;
    if(m == 0 && n == 0)
    return true;
    vector<vector<bool> > p(m + 1,vector<bool>(n + 1,false));
    for(int i =1; i <= m; ++i)
        p[i][0] = (s3[i - 1] == s1[i - 1]);
    for(int j =1; j <= n; ++j)
        p[0][j] = (s3[j - 1] == s2[j - 1]);
    for(int i =1; i <= m; ++i){
        for(int j =1; j <= n; ++j){
            if(s1[i - 1] == s2[j - 1]){
                if(s3[i + j - 1] == s1[i - 1])
                    p[i][j] = p[i - 1][j] || p[i][j - 1];
                    else
                    p[i][j] = false;
                }
                else{
                    if(s3[i + j - 1] == s1[i - 1])
                        p[i][j] = p[i - 1][j];
                    else if(s3[i + j - 1] == s2[j - 1])
                        p[i][j] = p[i][j - 1];
                    else
                        p[i][j] = false;
            }
        }
    }
    return p[m][n];
}

No comments:

Post a Comment