由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Leetcode Scramble String简单解法
相关主题
string scramble 的时间复杂度请教一个Palindrome Partition问题
scramble string 怎么用dp 阿?Palindrome Partitioning II 的DP做法?
有人面试碰到过scramble string这个题吗?Leetcode problems' difficulty
scramble的复杂度过两天就要 G家 onsite了
leetcode的scramble string的test cases是不是有问题?一道有关String的面试题
leetcode-- scramble stringrequest solutions to 2 questions on leetcode
scramble string关于leetcode的Scramble String问题
发包子请教大牛:scramble string这题递归的复杂度string interleave
相关话题的讨论汇总
话题: string话题: s1话题: scrambled话题: scramble话题: rgtae
进入JobHunting版参与讨论
1 (共1页)
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?

1 (共1页)
进入JobHunting版参与讨论
相关主题
string interleaveleetcode的scramble string的test cases是不是有问题?
二爷的scramble string能跑的起来么?leetcode-- scramble string
google scramble string O(n) 解法scramble string
请教那个scramble string的题目发包子请教大牛:scramble string这题递归的复杂度
string scramble 的时间复杂度请教一个Palindrome Partition问题
scramble string 怎么用dp 阿?Palindrome Partitioning II 的DP做法?
有人面试碰到过scramble string这个题吗?Leetcode problems' difficulty
scramble的复杂度过两天就要 G家 onsite了
相关话题的讨论汇总
话题: string话题: s1话题: scrambled话题: scramble话题: rgtae