Interleaving String

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.

C++:
01 class Solution {
02 public:
03     bool isInterleave(string s1, string s2, string s3) {
04         // Start typing your C/C++ solution below
05         // DO NOT write int main() function    
06         int n=s1.size();
07         int m=s2.size();
08         int p=s3.size();
09         if((n+m)!=p)
10             return false;
11         if(n<m)
12         {
13             string t=s1;
14             s1=s2;
15             s2=t;
16             n=n+m;
17             m=nm;
18             n=nm;
19         }
20         vector<bool*> A(m+1);
21         for(int i=0;i<=m;i++)
22         {
23             A[i]=new bool[n+1];
24         }
25         A[0][0]=true;
26         for(int i=1;i<=n;i++)
27         {
28             A[0][i]=A[0][i1]&&(s1[i1]==s3[i1]);
29         }
30         for(int i=1;i<=m;i++)
31         {
32             A[i][0]=A[i1][0]&&(s2[i1]==s3[i1]);
33         }
34         for(int i=1;i<=m;i++)
35         {
36             A[i][i]=(A[i1][i]&&(s2[i1]==s3[2*i1]))
37                     ||(A[i][i1]&&(s1[i1]==s3[2*i1]));
38             for(int j=i+1;j<=n;j++)
39             {
40                 A[i][j]=(A[i1][j]&&(s2[i1]==s3[i+j1]))
41                     ||(A[i][j1]&&(s1[j1]==s3[i+j1]));
42             }
43             for(int j=i+1;j<=m;j++)
44             {
45                 A[j][i]=(A[j1][i]&&(s2[j1]==s3[i+j1]))
46                     ||(A[j][i1]&&(s1[i1]==s3[i+j1]));
47             }
48         }
49         return A[m][n];
50     }
51 };
Advertisements
This entry was posted in Dynamic programming, String. Bookmark the permalink.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s