n 个字符串的最长公共前缀

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

示例：['花'、'流'、'你好'、'舰队']

答案：fl

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

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