f*********m
发帖数: 726 | |
f*********i
发帖数: 197 | 2 啊，这个blog是我写的，居然被翻出来了。
很惭愧，这个方法后来被人发现只能作用于unique character string，如果一个
string里面有duplication，那么就要做data pre-processing，找出所有可能的排列，
然后一一比较。 那样的话时间复杂度就高了。
我曾经考虑过用一个list来表达不同情况下的merge，但是发现这个方法太复杂，没有
头绪。
请高人赐教 |
f*********m
发帖数: 726 | 3 呵呵，谢谢啊，不过有些地方没太看懂。还得高人指教。 |
w****x
发帖数: 2483 | |
f*********m
发帖数: 726 | |
f*********i
发帖数: 197 | 6 我刚才想到了一个可以对付duplicated characters的方法，请看
http://csjobinterview.wordpress.com/2012/06/29/google-scramble-
思路还是不断的merge，从一个character开始不断向前或者向后延伸，看最终是否能够
还原目标string。
请各位不吝赐教 |
f*********m
发帖数: 726 | |
p********s
发帖数: 37 | 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*****3
发帖数: 1391 | 9 提个意见啊，能不能先讲讲思路，然后贴答案啊，读源代码也是件挺痛苦的事 |
f*********m
发帖数: 726 | |
x*******6
发帖数: 262 | 11 请问sramble string和anagram有什么区别？不能将string里面的char排序然后看是否
一样么？ |
e***s
发帖数: 799 | 12 大哥，您的code好像有问题， （"great", "rgaet"）应该是FALSE，但是返回TRUE了
【在 f*********i 的大作中提到】
: 我刚才想到了一个可以对付duplicated characters的方法，请看
: http://csjobinterview.wordpress.com/2012/06/29/google-scramble-
: 思路还是不断的merge，从一个character开始不断向前或者向后延伸，看最终是否能够
: 还原目标string。
: 请各位不吝赐教
|
e***s
发帖数: 799 | 13 请教各位，对题目有一点不太清楚的是，如果选了一个节点的children还有children，
是否一定要swap到底。
比如
great
/ \
gr eat
/\ /\
g r e at
/\
a t
如果选择"eat"这个节点，只swap"e" 和 "at"，生成"grate"可以吗？还是一定要把 "a
" 和 "t" swap，最后生成"grtae"? |
