Redian新闻
>
关于leetcode的Scramble String问题
avatar
f*i
2
啊,这个blog是我写的,居然被翻出来了。
很惭愧,这个方法后来被人发现只能作用于unique character string,如果一个
string里面有duplication,那么就要做data pre-processing,找出所有可能的排列,
然后一一比较。 那样的话时间复杂度就高了。
我曾经考虑过用一个list来表达不同情况下的merge,但是发现这个方法太复杂,没有
头绪。
请高人赐教
avatar
f*m
3
呵呵,谢谢啊,不过有些地方没太看懂。还得高人指教。
avatar
f*m
5
能说说思路吗?
avatar
p*s
8
刚试了下,用预处理+暴力搜索可以忽悠过去
预处理:对于s1,s2的所有位置p1,p2和长度l有子串(p1,p1+l)和(p2,p2+l),如果两个
子串包含不同的字符集则搜索时不予考虑
搜索:对于s1,s2,以及可能的字串长度l,递归搜索以下两种情况:
把s1和s2拆成l和strlen(s1)-l两段,分别递归搜索
把s1拆成l和strlen(s1)-l两段,把s2拆成strlen(s2-l)和l两段,分别递归搜索
avatar
h*3
9
提个意见啊,能不能先讲讲思路,然后贴答案啊,读源代码也是件挺痛苦的事
avatar
f*m
10
同求code和思路。谢谢。
avatar
x*6
11
请问sramble string和anagram有什么区别?不能将string里面的char排序然后看是否
一样么?
avatar
e*s
12
大哥,您的code好像有问题, ("great", "rgaet")应该是FALSE,但是返回TRUE了

【在 f*********i 的大作中提到】
: 我刚才想到了一个可以对付duplicated characters的方法,请看
: http://csjobinterview.wordpress.com/2012/06/29/google-scramble-
: 思路还是不断的merge,从一个character开始不断向前或者向后延伸,看最终是否能够
: 还原目标string。
: 请各位不吝赐教

avatar
e*s
13
请教各位,对题目有一点不太清楚的是,如果选了一个节点的children还有children,
是否一定要swap到底。
比如
great
/ \
gr eat
/\ /\
g r e at
/\
a t
如果选择"eat"这个节点,只swap"e" 和 "at",生成"grate"可以吗?还是一定要把 "a
" 和 "t" swap,最后生成"grtae"?
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。