的最大长度为m给定n个字符串。我们怎样才能找到最长的共同preFIX由至少两个字符串共享其中？

Given n string of max length m. How can we find the longest common prefix shared by at least two strings among them?

例：['花'，'流动'，'你好'，'舰队']

Example: ['flower', 'flow', 'hello', 'fleet']

答：FL

我想建立一个特里的所有字符串，然后检查最深的节点（满足最长的），其分出两个/多子（满足共性）的。这需要O（N * M）的时间和空间。有没有更好的方式来做到这一点。

I was thinking of building a Trie for all the string and then checking the deepest node (satisfies longest) that branches out to two/more substrings (satisfies commonality). This takes O(n*m) time and space. Is there a better way to do this

推荐答案

有一个 O（| S | * N）解决这个问题，使用线索。 [ N 是一个字符串的数字，取值是最长的字符串]

there is an O(|S|*n) solution to this problem, using a trie. [n is the number of strings, S is the longest string]

(1) put all strings in a trie
(2) do a DFS in the trie, until you find the first vertex with more then 1 "edge".
(3) the path from the root to the node you found at (2) is the longest commin prefix.

有没有可能更快的解决方案，然后它[在大O符号的条款]，在最坏的情况下，所有的字符串是相同的 - 你需要阅读所有的人都知道这一点。

There is no possible faster solution then it [in terms of big O notation], at the worst case, all your strings are identical - and you need to read all of them to know it.