新手请教：请推荐Nikon D90套装# PhotoGear - 摄影器材
r*n
1 楼
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.
我觉得最简单（近乎于trivial）的解法是看两个string是否含有相同的alphabet
count，如果相同，则s2是s1的scrambled string。
大致逻辑是：
如果S1是n个字符，全排列也最多就n!： T(n) = n*T(n-1)
但是S1所有的scramble tree比n!还多： T(n) = ( T(n-1)*...*T(1) )^2
但这未免太简单了，是不是考虑掉了某些情况？
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.
我觉得最简单（近乎于trivial）的解法是看两个string是否含有相同的alphabet
count，如果相同，则s2是s1的scrambled string。
大致逻辑是：
如果S1是n个字符，全排列也最多就n!： T(n) = n*T(n-1)
但是S1所有的scramble tree比n!还多： T(n) = ( T(n-1)*...*T(1) )^2
但这未免太简单了，是不是考虑掉了某些情况？
