Determine interleave

Given string a, string b and string c. Determine if c is the interleave of a and b.

C++:
01 bool interLeave(string a, string b, string c)
02 {
03     if(a.size()+b.size()!=c.size())
04         return false;
05     if(a.size()==0)
06         return (b==c);
07     if(b.size()==0)
08         return (a==c);
09     bool p=false;
10     bool q=false;
11     if(a[0]==c[0]){
12         string d=a.substr(1);
13         string e=c.substr(1);
14         p=interLeave(d,b,e);
15     }
16     if(b[0]==c[0]){
17         string d=b.substr(1);
18         string e=c.substr(1);
19         q=interLeave(a,d,e);
20     }
21     return p||q;
22 }

The above code is a recursive way of solving dynamic programming, which is not efficient. We need to build a iterative way to solve this problem!

C++:
01 bool isInterleave(string s1, string s2, string s3)
02 {
03         int a=s1.size();
04         int b=s2.size();
05         int c=s3.size();
06         if(a+b!=c)
07             return false;
08         bool A[a+1][b+1];
09         for(int i=0;i<=a;i++)
10             for(int j=0;j<=b;j++)
11                 A[i][j]=false;
12         A[a][b]=true;
13         for(int i=a1;i>=0;i){
14             if((s1[i]==s3[i+ca])&&(A[i+1][b]==true))
15                 A[i][b]=true;
16         }
17         for(int i=b1;i>=0;i){
18             if((s2[i]==s3[i+cb])&&(A[a][i+1]==true))
19                 A[a][i]=true;
20         }
21         for(int i=a1;i>=0;i){
22             for(int j=b1;j>=0;j){
23                 if((s1[i]==s3[i+j])&&(A[i+1][j]==true))
24                     A[i][j]=true;
25                 else if((s2[j]==s3[i+j])&&(A[i][j+1]==true))
26                     A[i][j]=true;
27             }
28         }
29         return A[0][0];
30 }
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