n字符串的最长公共前缀

Question

给定n串最大长度m.我们怎样才能找到其中至少有两个字符串共享的最长公共前缀？

示例:['flower','flow','hello','fleet']

答:fl

我正在考虑为所有字符串构建Trie,然后检查分支到两个/更多子串的最深节点(满足最长)(满足通用性).这需要O(n*m)的时间和空间.有一个更好的方法吗

Answer 1

有一个O(|S|*n)解决这个问题,采用了线索.[ n是字符串的数量,S是最长的字符串]

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

没有可能更快的解决方案 [就大O表示而言],在最坏的情况下,所有的字符串都是相同的 - 你需要阅读所有字符串才能知道它.

Answer 2

为什么要使用trie(需要O(mn)时间和O(mn)空间,只需使用基本的暴力方式.首先循环,找到最短的字符串为minStr,这需要o(n)时间,第二个循环,比较一个用这个minStr做一个,并保留一个表示minStr最右边索引的变量,这个循环取O(mn),其中m是所有字符串的最短长度.代码如下,

public String longestCommonPrefix(String[] strs) {
    if(strs.length==0) return "";
    String minStr=strs[0];

    for(int i=1;i<strs.length;i++){
        if(strs[i].length()<minStr.length())
            minStr=strs[i];
    }
    int end=minStr.length();
    for(int i=0;i<strs.length;i++){
        int j;
        for( j=0;j<end;j++){
            if(minStr.charAt(j)!=strs[i].charAt(j))
                break;
        }
        if(j<end)
            end=j;
    }
    return minStr.substring(0,end);
}

Answer 3

我会对它们进行排序,你可以及时做到n lg n.那么具有共同前缀的任何字符串都将紧挨着彼此.实际上,您应该能够保留一个指针,指出您当前正在查看哪个索引,然后按计划进行快速计算.