algorithm - n 个字符串的最长公共(public)前缀

Question

给定 n 个最大长度为 m 的字符串。我们如何找到其中至少两个字符串共享的最长公共(public)前缀？

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

答案:fl

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

Answer 1

为什么要用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);
}