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.
思考：递归。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 |
class
Solution {public: bool
isScramble(string s1, string s2) { if(s1.size()!=s2.size()) return
false; if(s1==s2) return
true; //if(字符不相同) return false; string str1=s1;sort(str1.begin(),str1.end()); string str2=s2;sort(str2.begin(),str2.end()); if(str1!=str2) return
false; int
len=s1.size(),i; for(i=1;i<len;i++) { //if（左左&&右右)||(左右&&右左) return true; if((isScramble(s1.substr(0,i),s2.substr(0,i))&&isScramble(s1.substr(i),s2.substr(i))) ||(isScramble(s1.substr(0,i),s2.substr(len-i))&&isScramble(s1.substr(i),s2.substr(0,len-i)))) return
true; } return
false; }}; |
[LeetCode]Scramble String,布布扣,bubuko.com
原文：http://www.cnblogs.com/Rosanna/p/3593527.html