Interleaving String

3

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.

asked 31 Aug '12, 00:40

1337c0d3r's gravatar image

1337c0d3r ♦♦
1.2k●5●82●171
accept rate: 2%

27 Answers:
oldestnewestmost voted

123next »

3

Linear memory cost

class Solution {

public:

bool isInterleave(string s1, string s2, string s3) 
{
    int m = s1.size();
    int n = s2.size();
    int l = s3.size();
    if (m + n != l )
        return false;
    vector<bool> M(n+1);
    M[n] = true;
    for (int j=n-1; j>=0; j--)
        if (!(M[j] = s3[m+j] == s2[j] && M[j+1]))
            break;

    for (int i=m-1; i >=0; i--)
    {
        for (int j=n-1; j>=0; j--)
        {
            if ( s3[i+j] == s1[i] && M[j] )
                M[j] = true;
            else if ( s3[i+j] == s2[j] && M[j+1] )
                M[j] = true;      
            else
                M[j] = false;
        }
        M[n] = s3[n+i] == s1[i] && M[n];
    }
    return M[0];                 
}

};

link

answered 21 Jan, 19:50

parksight's gravatar image

parksight
36●1
accept rate: 0%

1

Anyone can tell me why here array is almost twice faster than vector?

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1(s1.size()),n2(s2.size()),n3(s3.size());
        if(n3!=n1+n2) return false;
        bool d[n1+1][n2+1];
        bzero(d,(n1+1)*(n2+1)*sizeof(bool));
        d[0][0]=true;

        for(int i=0;i<n1;++i)
            if(s1[i]==s3[i]) d[i+1][0]=true;
            else break;

        for(int i=0;i<n2;++i)
            if(s2[i]==s3[i]) d[0][i+1]=true;
            else break;

        for(int i=1;i<=n1;++i)
            for(int j=1;j<=n2;++j)
                d[i][j]=(d[i][j-1]&&s3[i+j-1]==s2[j-1])||(d[i-1][j]&&s3[i+j-1]==s1[i-1]);

        return d[n1][n2];
    }
};
link

answered 03 Jan, 14:48

Jingfei%20Jia's gravatar image

Jingfei Jia
116●2●5
accept rate: 0%

I think array is primitive so less overhead than vector

(02 Feb, 00:04) jjlights jjlights's gravatar image
1 
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 len1=s1.size(), len2=s2.size(), len3=s3.size();        
    if(len1+len2 != len3) return false;

    //switch to save space later on.
    if(len2>len1)  {string tmp=s2; s2=s1; s1=tmp;}

    vector<bool> isPrefix(s2.size()+1, false);
    isPrefix[0]=true;

    for(int i=1; i<=s2.size(); i++) isPrefix[i] = s2.substr(0, i) == s3.substr(0, i);

    for(int i=1; i<=s1.size(); i++){
        isPrefix[0] = s1.substr(0, i)==s3.substr(0,i);
        for(int j=1; j<=s2.size(); j++)
            isPrefix[j]= (isPrefix[j-1]&&s2[j-1]==s3[i+j-1] || isPrefix[j]&&s1[i-1]==s3[i+j-1]);
    }
    return isPrefix.back();
}
};
link

answered 02 Mar, 02:57

lchh's gravatar image

lchh
32●3
accept rate: 0%

edited 02 Mar, 03:01

isPrefix(i,j) indicates s1.substr(0, i)+s2.substr(0,j)==s3.substr(0,i+j);

isPrefix(i,j) = isPrefix(i-1,j)&&s1[i-1]==s3[i+j-1] || isPrefix(i,j-1)&&s2[j-1]==s3[i+j-1]

Here, only an array is used to simplify the space overhead (O(min(len1, len2)))

(02 Mar, 03:01) lchh lchh's gravatar image
0 
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.length() + s2.length() != s3.length()) return false;
        if (s1.empty() || s2.empty()) return (!s1.compare(s3) || !s2.compare(s3));

        s1 = "S"+s1;
        s2 = "S"+s2;
        s3 = "S"+s3;//index starts from 1
        vector<vector<bool> > v(s1.length()+1, vector<bool>(s2.length()+1, false));
        v[0][0]=true;
        for(int ii = 1; ii < s2.length(); ++ii){
            if (s2[ii] == s3[ii]) v[0][ii] = v[0][ii-1];
        }
        for(int ii = 1; ii < s1.length(); ++ii){
            if (s1[ii] == s3[ii]) v[ii][0] = v[ii-1][0];
        }
        for(int ii = 1; ii <s1.length(); ++ii){
            for(int jj = 1; jj <s2.length(); ++jj){
                if (s1[ii] == s3[ii+jj]) v[ii][jj] = v[ii][jj] || v[ii-1][jj];
                if (s2[jj] == s3[ii+jj]) v[ii][jj] = v[ii][jj] || v[ii][jj-1];
            }
        }
        return v[s1.length()-1][s2.length()-1];
    }
};
link

answered 31 Dec '12, 09:16

cppInitiator's gravatar image

cppInitiator
147●3●3
accept rate: 0%

0 
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.length()+s2.length() != s3.length()) return false;
        if(s3.length() == 0) return true;
        vector<vector<bool> > mt(s1.length()+1, vector<bool>(s2.length()+1, false));        
        for(int i = 0; i < s1.length(); i++) 
            if(s1[i] == s3[i]) mt[i+1][0] = true;
            else break;
        for(int j = 0; j < s2.length(); j++) 
            if(s2[j] == s3[j]) mt[0][j+1] = true;
            else break;             
        for(int i = 2; i < s3.length()+1; i++) 
            for(int j = max(1, i-int(s2.length())); j < min(i, int(s1.length()+1)); j++) {
                if(s1[j-1] == s3[i-1]) mt[j][i-j] = mt[j][i-j]||mt[j-1][i-j];
                if(s2[i-j-1] == s3[i-1]) mt[j][i-j] = mt[j][i-j]||mt[j][i-j-1];
            }               
        return mt[s1.length()][s2.length()];        
    }
};
link

answered 02 Jan, 19:51

ktu's gravatar image

ktu
146●2●5
accept rate: 0%

0 
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
    // Start typing your Java solution below
    // DO NOT write main() function
    if (s1.length()+s2.length()!=s3.length()) return false;
    if (s1.length()==0&&s2.length()==0&&s3.length()==0) return true;
    boolean[][] A = new boolean[s2.length()+1][s1.length()+1];
    A[0][0]=false;
    for (int i=0;i<s1.length();i++) {
        if ((i==0 || A[0][i]==true) && (s1.charAt(i)==s3.charAt(i))) {
            A[0][i+1]=true;
        } else
            A[0][i+1]=false;
    }
    for (int i=0;i<s2.length();i++) {
        if ((i==0 || A[i][0]==true) && (s2.charAt(i)==s3.charAt(i))) {
            A[i+1][0]=true;
        } else
            A[i+1][0]=false;
    }
    for (int i=0;i<s2.length();i++) {
        for (int j=0;j<s1.length();j++) {
            if (A[i][j+1] && s2.charAt(i)==s3.charAt(i+j+1)) {
                    A[i+1][j+1]=true;
            } else if (A[i+1][j]) {
                 if (s1.charAt(j)==s3.charAt(i+j+1))
                    A[i+1][j+1]=true;
                 else 
                    A[i+1][j+1]=false;
            } else 
                A[i+1][j+1]=false;
        }
    }
    return A[s2.length()][s1.length()];
}
}
link

answered 02 Feb, 00:03

jjlights's gravatar image

jjlights
10●2
accept rate: 0%

0 
public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length() + s2.length() != s3.length())
            return false;
        boolean[] interleaved = new boolean[s2.length() + 1];
        interleaved[0] = true;
        for(int i = 0; i <= s1.length(); i++)
            for(int j = 0; j <= s2.length(); j++){
                if(i - 1 >= 0)
                    interleaved[j] = interleaved[j] & (s1.charAt(i - 1) == s3.charAt(i + j - 1));
                if(j - 1 >= 0)
                    interleaved[j] |= interleaved[j - 1] & (s2.charAt(j - 1) == s3.charAt(i + j - 1));
            }

        return interleaved[s2.length()];
    }
link

answered 12 Feb, 12:39

bysun's gravatar image

bysun
91●3
accept rate: 0%

0

Although my recursive is time-exceeded, it is just provided for a idea...

bool isInterleave(string s1, string s2, string s3) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function    
    return checkForInterleave(s1, s2, s3, 0, 0, 0);
}

bool checkForInterleave(string s1, string s2, string s3, int i, int j, int k) {

    if (i>=s1.length() && j>=s2.length() && k>=s3.length())
        return true;

    bool ret = false;

    if(s1[i] == s3[k] && s2[j] != s3[k]) {
        ret = checkForInterleave(s1, s2, s3, i+1, j, k+1);
    }
    else if (s1[i] != s3[k] && s2[j] == s3[k]) {
        ret = checkForInterleave(s1, s2, s3, i, j+1, k+1);
    }
    else if (s1[i] == s2[j] && s1[i] == s3[k]) {
        ret = checkForInterleave(s1, s2, s3, i+1, j, k+1);
        if (!ret)
            ret = checkForInterleave(s1, s2, s3, i, j+1, k+1);
    }
    else {
        ret = false;
    }
    return ret;
}
link

answered 12 Feb, 20:01

Shengzhe%20Chen's gravatar image

Shengzhe Chen
112●4
accept rate: 4%

0 
public boolean isInterleave(String s1, String s2, String s3) {
    int m = s1.length();
    int n = s2.length();
    int s = s3.length();
    if(m + n != s)
        return false;

    boolean[][] dp = new boolean[n + 1][m + 1];
    dp[0][0] = true;

    for(int i = 0; i < n + 1; i++)
        for(int j = 0; j < m + 1; j++) {
            if(dp[i][j] || (i - 1 >= 0 && dp[i - 1][j] == true && s2.charAt(i - 1) == s3.charAt(i + j - 1)) || ( j - 1 >= 0 && dp[i][j - 1] == true && s1.charAt(j - 1) == s3.charAt(i + j - 1)))
                dp[i][j] = true;
            else
                dp[i][j] = false;
    }

    return dp[n][m];
}
link

answered 20 Feb, 21:30

entourage's gravatar image

entourage
51●1●4
accept rate: 0%

0

Most ugly one, HAHA

bool isInterleave(string s1, string s2, string s3) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function    
    bool s1_flag, s2_flag;

    if (s1.length() + s2.length() != s3.length()) {
        return false;
    }

    if (s3.length() == 0) {
        return true;
    }

    s1_flag = (s1.length() == 0) ? true : (s1[0] == s3[0]);
    s2_flag = (s2.length() == 0) ? true : (s2[0] == s3[0]);

    if (s1.length() == 0) {
        if (!s2_flag) {
            return false;
        }
        return isInterleave(s1, string(s2, 1, s2.length()-1),
                    string(s3, 1, s3.length()-1));
    } else if (s2.length() == 0) {
        if (!s1_flag) {
            return false;
        }
        return isInterleave(string(s1, 1, s1.length()-1),
                    s2, string(s3, 1, s3.length()-1));
    } else {
        if (s1_flag && s2_flag) {
            return isInterleave(string(s1, 1, s1.length()-1),
                        s2, string(s3, 1, s3.length()-1)) ||
                    isInterleave(s1, string(s2, 1, s2.length()-1),
                        string(s3, 1, s3.length()-1));
        } else if (s1_flag) {
            return isInterleave(string(s1, 1, s1.length()-1),
                    s2, string(s3, 1, s3.length()-1));
        } else if (s2_flag) {
            return isInterleave(s1, string(s2, 1, s2.length()-1),
                    string(s3, 1, s3.length()-1));
        } else {
            return false;
        }
    }
}
link

answered 25 Feb, 22:08

whitebluff's gravatar image

whitebluff
21●2
accept rate: 0%

123next »

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • Indent code by 4 spaces.
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

learn more about Markdown

Tags:

×139

Asked: 31 Aug '12, 00:40

Seen: 3,923 times

Last updated: yesterday

Related questions

Populating Next Right Pointers in Each Node

Median of Two Sorted Arrays

3Sum Closest

Search for a Range

N-Queens

Sqrt(x)

Partition List

Path Sum

Surrounded Regions

3Sum

about | faq | privacy | contact