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"? |