Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = “great”:

great
/      \
gr       eat
/ \       /   \
g    r     e     at
/ \
a    t
To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node “gr” and swap its two children, it produces a scrambled string “rgeat”.

rgeat
/     \
rg      eat
/ \      / \
r     g   e   at
/ \
a     t
We say that “rgeat” is a scrambled string of “great”.

Similarly, if we continue to swap the children of nodes “eat” and “at”, it produces a scrambled string “rgtae”.

rgtae
/   \
rg     tae
/ \     / \
r    g  ta   e
/ \
t   a
We say that “rgtae” is a scrambled string of “great”.

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

C++:
01 bool isScramble(string s1, string s2)
02  {
03       if(s1.size()!=s2.size())
04           return false;
05       int n=s1.size();
06       if(n==1)
07           return (s1==s2);
08       int A[26];
09       for(int i=0;i<26;i++)
10           A[i]=0;
11       for(int i=0;i<n;i++){
12           int p=s1[i]‘a’;
13           A[p]++;
14       }
15       for(int i=0;i<n;i++){
16           int p=s2[i]‘a’;
17           A[p];
18           if(A[p]<0)
19               return false;
20       }
21       for(int i=1;i<=n1;i++)
22       {
23           string a=s1.substr(0,i);
24           string b=s1.substr(i,ni);
25           string c=s2.substr(0,i);
26           string d=s2.substr(i,ni);
27           string e=s2.substr(0,ni);
28           string f=s2.substr(ni,i);
29           if(isScramble(a,c)&&isScramble(b,d)==true)
30               return true;
31           if(isScramble(a,f)&&isScramble(b,e)==true)
32               return true;
33       }
34       return false;
35 }
Advertisements
This entry was posted in Recursive, 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