问个google老题的最佳解法 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个google老题的最佳解法

问个google老题的最佳解法# JobHunting - 待字闺中

B*12011-10-11 07:10

1 楼

Write a function to find the longest common prefix string amongst an array
of strings
是不是找最短那个string，从第一个字母开始每个string那样子compare，如果都有就
加到prefix，直到遇到有不一样或者'\0' 啊。
thanks

f*52011-10-11 07:10

2 楼

Create a prefix tree or Tier for the string array
for each node,set the value to the number the strings
start from its path

【在 B*******1 的大作中提到】

: Write a function to find the longest common prefix string amongst an array
: of strings
: 是不是找最短那个string，从第一个字母开始每个string那样子compare，如果都有就
: 加到prefix，直到遇到有不一样或者'\0' 啊。
: thanks

B*12011-10-11 07:10

3 楼

我觉得这个不是最好的吧？
这样子多了很多无用的操作
譬如
ab
abc
abe
abf
abg
abweruioweujksf
abjksjdfkjkwlejlkwje
abmnenremwnrmwen
其实prefix就是ab，但是如果每个都插入trie，后面可能很多很长的string根本没有
insert全部字符的必要吧。

B*12011-10-11 07:10

4 楼

一开始的2个string的common prefix是ab，后面的common prefix也最多只能够是ab，
后面长的那些还需要看ab后面那些string吗？

f*52011-10-11 07:10

5 楼

a
b
c e
建trie到这个时候，也就可以知道最多是ab了

【在 B*******1 的大作中提到】

: 一开始的2个string的common prefix是ab，后面的common prefix也最多只能够是ab，
: 后面长的那些还需要看ab后面那些string吗？

B*12011-10-11 07:10

6 楼

那么后面这些还要全部插入trie里面吗？
abweruioweujksf
abjksjdfkjkwlejlkwje
abmnenremwnrmwen

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

: a
: b
: c e
: 建trie到这个时候，也就可以知道最多是ab了

f*52011-10-11 07:10

7 楼

你说呢？
你不是找了最短的串也不想比较多余的部分吗？

【在 B*******1 的大作中提到】

: 那么后面这些还要全部插入trie里面吗？
: abweruioweujksf
: abjksjdfkjkwlejlkwje
: abmnenremwnrmwen

B*12011-10-11 07:10

8 楼

那么我觉得用trie跟从第一个字符开始，每个字符串那么比的复杂度一样啊。但是trie
还需要额外memory。
譬如
abg
abc
abe
abf
abg
abweruioweujksf
abjksjdfkjkwlejlkwje
abmnenremwnrmwen
从a开始，每个字符都有 prefix ＝ a
从b开始，每个字符都有 prefix ＝ ab
从g开始，g和c不match，返回