r*********n 发帖数: 4553 | 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
但这未免太简单了,是不是考虑掉了某些情况? | e*******8 发帖数: 94 | 2 How about "bcde" to "cebd"? the latter is not a scramble string of the
former? | r*********n 发帖数: 4553 | 3 i see, thanks
【在 e*******8 的大作中提到】 : How about "bcde" to "cebd"? the latter is not a scramble string of the : former?
|
|