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 的大作中提到】
: 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 的大作中提到】
: 一开始的2个string的common prefix是ab，后面的common prefix也最多只能够是ab，
: 后面长的那些还需要看ab后面那些string吗？
|
B*******1
发帖数: 2454 | 6 那么后面这些还要全部插入trie里面吗？
abweruioweujksf
abjksjdfkjkwlejlkwje
abmnenremwnrmwen
【在 f*********5 的大作中提到】
: a
: b
: c e
: 建trie到这个时候，也就可以知道最多是ab了
|
f*********5
发帖数: 576 | 7 你说呢？
你不是找了最短的串也不想比较多余的部分吗？
【在 B*******1 的大作中提到】
: 那么后面这些还要全部插入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，返回 |
