LeetCode题解——14. 最长公共前缀_如何用前缀树来解决最长前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。

示例

示例 1:

输入: [“flower”,“flow”,“flight”]
输出: “fl”

示例 2:

输入: [“dog”,“racecar”,“car”]
输出: “”
解释: 输入不存在公共前缀。

说明:所有输入只包含小写字母 a-z 。

思路

思路一

    根据语义，很容易想到的是两两查找，最后找出最长公共前缀，时间复杂度为O(n^2)代码如下：

public String longestCommonPrefix(String[] strs) {
         if (strs.length==0){
            return "";
        }
        int maxStringLength=0;
        String maxString=null;
        int []maxMatchLength=new int[strs.length];
        for (int i=0;i<strs.length;i++){
            if (strs[i].length()>maxStringLength){
                maxStringLength=strs[i].length();
                maxString=strs[i];
            }
        }
        for (int i=0;i<strs.length;i++){
            int index=0;
            for (int j=0;j<strs[i].length();j++){
                if (strs[i].charAt(j) == maxString.charAt(j)){
                    index++;
                }
                if (strs[i].charAt(j) != maxString.charAt(j)){
                    break;
                }
            }
            maxMatchLength[i]=index;
        }
        maxStringLength=maxMatchLength[0];
        for (int i=0;i<strs.length;i++){
            if (maxMatchLength[i]<maxStringLength){
                maxStringLength=maxMatchLength[i];
            }
        }
        if (maxStringLength==0){
            return "";
        }
        return maxString.substring(0,maxStringLength);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

思路二

    在思路一的基础上，进行垂直扫描，也就是按顺序取出一个字符进行所有字符串的比较，就能使得时间复杂度变成最短字符串长度*字符串数量，而且避免了思路一大部分不必要的比较，代码如下：

public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0){
            return "";
        }
        StringBuilder str=new StringBuilder("");
        int length=strs[0].length();
        for (int i=0; i<strs.length; i++){
            length=strs[i].length() < length ? strs[i].length():length;
        }
        int i=0;
        while (i < length){
            char t=strs[0].charAt(i);
            for (int j=0; j<strs.length; j++){
                if(t != strs[j].charAt(i)){
                    return str.toString();
                }
            }
            str.append(t);
            i++;
        }
        return str.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路三

    利用前缀树的实现，当产生分支时，取产生分支前的字符串即为最长公共前缀，如[A,B,C,D]，[A,B,C]，[A,C]的前缀树：