B*******1 发帖数: 2454 | 1 Write a function to find the longest common prefix string amongst an array
of strings
是不是找最短那个string,从第一个字母开始每个string那样子compare,如果都有就
加到prefix,直到遇到有不一样或者'\0' 啊。
thanks |
f*********5 发帖数: 576 | 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Write a function to find the longest common prefix string amongst an array : of strings : 是不是找最短那个string,从第一个字母开始每个string那样子compare,如果都有就 : 加到prefix,直到遇到有不一样或者'\0' 啊。 : thanks
|
B*******1 发帖数: 2454 | 3 我觉得这个不是最好的吧?
这样子多了很多无用的操作
譬如
ab
abc
abe
abf
abg
abweruioweujksf
abjksjdfkjkwlejlkwje
abmnenremwnrmwen
其实prefix就是ab,但是如果每个都插入trie,后面可能很多很长的string根本没有
insert全部字符的必要吧。 |
B*******1 发帖数: 2454 | 4 一开始的2个string的common prefix是ab,后面的common prefix也最多只能够是ab,
后面长的那些还需要看ab后面那些string吗? |
f*********5 发帖数: 576 | 5 a
b
c e
建trie到这个时候,也就可以知道最多是ab了
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 一开始的2个string的common prefix是ab,后面的common prefix也最多只能够是ab, : 后面长的那些还需要看ab后面那些string吗?
|
B*******1 发帖数: 2454 | 6 那么后面这些还要全部插入trie里面吗?
abweruioweujksf
abjksjdfkjkwlejlkwje
abmnenremwnrmwen
【在 f*********5 的大作中提到】![](/moin_static193/solenoid/img/up.png) : a : b : c e : 建trie到这个时候,也就可以知道最多是ab了
|
f*********5 发帖数: 576 | 7 你说呢?
你不是找了最短的串也不想比较多余的部分吗?
【在 B*******1 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那么后面这些还要全部插入trie里面吗? : abweruioweujksf : abjksjdfkjkwlejlkwje : abmnenremwnrmwen
|
B*******1 发帖数: 2454 | 8 那么我觉得用trie跟从第一个字符开始,每个字符串那么比的复杂度一样啊。但是trie
还需要额外memory。
譬如
abg
abc
abe
abf
abg
abweruioweujksf
abjksjdfkjkwlejlkwje
abmnenremwnrmwen
从a开始,每个字符都有 prefix = a
从b开始,每个字符都有 prefix = ab
从g开始,g和c不match,返回 |