Description
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 tTo 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 tWe 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 aWe 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.
Solution
1 class Solution {
2 public:
3 bool isScramble(string s1, string s2) {
4 if (s1 == s2)
5 return true;
6 if (revserse_equal(s1, s2))
7 return true;
8
9 int len = s1.size();
10
11 int count[26];
12 memset(count, 0, sizeof(int) * 26);
13 for (int i = 0; i < len; ++ i){
14 count[s1[i]-'a'] ++;
15 count[s2[i]-'a'] --;
16 }
17 // check if the frequency of letters are the same in s1 and s2
18 for (int i = 0; i < 26; ++ i)
19 if (count[i] )
20 return false;
21
22 if (len == 1)
23 return true;
24
25 bool flg = false;
26 for (int par = 1; par < len; ++ par){ // select the partition point
27 flg = flg || judge(par, s1, s2);
28 if (flg)
29 return flg;
30 }
31 return flg;
32 }
33 bool judge(int par, string &s1, string &s2){
34 int len = s1.size();
35 bool flg = isScramble(s1.substr(0, par), s2.substr(0, par)) && \
36 isScramble(s1.substr(par, len - par),s2.substr(par, len - par));
37 flg = flg || ( isScramble(s1.substr(0, par), s2.substr(len - par, par)) &&\
38 isScramble(s1.substr(par, len - par), s2.substr(0, len - par)) );
39 return flg;
40 }
41 bool revserse_equal(string s1, string s2){
42 for (int i = 0; i < s1.length(); ++ i){
43 if (s1[i] != s2[s1.length()-1 - i])
44 return false;
45 }
46 return true;
47 }
48 };Analysis
This is a recursive solution. We iteratively select a partition point at each level and divide each string into two substrings. As we can swap the children of any non-leaf node, we have to judge recursively if
1.(Children not swapped) s1[0, par-1] == s2[0, par-1] AND s1[par, end] == s2[par, end]
2.(Children swapped) s1[0, par-1] == s2[len - par, end] AND s1[par, end] == s2[0, par-1]
S1 would be a SS of S2 if either of (1) and (2) is satisfied.
There also exists DP solution to this problem.
