关于leetcode的Scramble String问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

关于leetcode的Scramble String问题

关于leetcode的Scramble String问题# JobHunting - 待字闺中

f*m2012-06-29 07:06

1 楼

在网上找到一个方法，但不知是否正确（http://csjobinterview.wordpress.com/2012/05/07/google-scramble-string/），大家有什么好的方法吗？
谢谢。

f*i2012-06-29 07:06

2 楼

啊，这个blog是我写的，居然被翻出来了。
很惭愧，这个方法后来被人发现只能作用于unique character string，如果一个
string里面有duplication，那么就要做data pre-processing，找出所有可能的排列，
然后一一比较。那样的话时间复杂度就高了。
我曾经考虑过用一个list来表达不同情况下的merge，但是发现这个方法太复杂，没有
头绪。
请高人赐教

f*m2012-06-29 07:06

3 楼

呵呵，谢谢啊，不过有些地方没太看懂。还得高人指教。

w*x2012-06-29 07:06

4 楼

http://haixiaoyang.wordpress.com/2012/04/30/scramble-string-pro
贴一个我做的

f*m2012-06-29 07:06

5 楼

能说说思路吗？

f*i2012-06-29 07:06

6 楼

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

f*m2012-06-29 07:06

7 楼

好像过不了OJ啊：（

【在 w****x 的大作中提到】

: http://haixiaoyang.wordpress.com/2012/04/30/scramble-string-pro
: 贴一个我做的

p*s2012-06-29 07:06

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两段，分别递归搜索

h*32012-06-29 07:06

9 楼

提个意见啊，能不能先讲讲思路，然后贴答案啊，读源代码也是件挺痛苦的事

f*m2012-06-29 07:06

10 楼

同求code和思路。谢谢。

x*62012-06-29 07:06

11 楼

请问sramble string和anagram有什么区别？不能将string里面的char排序然后看是否
一样么？

e*s2012-06-29 07:06

12 楼

大哥，您的code好像有问题，（"great", "rgaet"）应该是FALSE，但是返回TRUE了

【在 f*********i 的大作中提到】

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

e*s2012-06-29 07:06

13 楼

请教各位，对题目有一点不太清楚的是，如果选了一个节点的children还有children，
是否一定要swap到底。
比如
great
/ \
gr eat
/\ /\
g r e at
/\
a t
如果选择"eat"这个节点，只swap"e" 和 "at"，生成"grate"可以吗？还是一定要把 "a
" 和 "t" swap，最后生成"grtae"?