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.
第二次写这个题了,上次为了不反复生成string对象,用下标来做的,确实要复杂一些。
http://blog.csdn.net/a83610312/article/details/8858378
这次干脆图简单在递归中反复生成string对象,从提交的结果来看,还不是很慢,但其实还是建议用下标来做。
class Solution { public: bool isScramble(string s1, string s2) { // Start typing your C/C++ solution below // DO NOT write int main() function if (s1.compare(s2)==0) return true; string t1(s1),t2(s2); sort(t1.begin(),t1.end()); sort(t2.begin(),t2.end()); if ( t1.compare(t2)!=0) return false; int n=s1.length(); for(int i=1;i<n;i++) { string ls1=s1.substr(0,i); string rs1=s1.substr(i,n-i); string ls2=s2.substr(0,i); string rs2=s2.substr(i,n-i); if ( isScramble(ls1,ls2)&&isScramble(rs1,rs2)) return true; string ls22=s2.substr(0,n-i); string rs22=s2.substr(n-i,i); if ( isScramble(ls1,rs22)&&isScramble(rs1,ls22)) return true; } return false; } };