# 14.Longest Common Prefix 最长公共前缀

# 1. 题目详情

leetcode题目地址 (opens new window)

📗difficulty：Easy

🎯Tags：

String (opens new window)
分治思想

题目描述：

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

样例1：

输入: ["flower","flow","flight"]
输出: "fl"

1
2

样例2：

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

1
2
3

# 2. 优秀解答：

以下题解为 leetcoe-cn 官方题解 (opens new window)。

# 2.1 水平扫描法

📃帖子原址 (opens new window)

核心代码：

public String longestCommonPrefix(String[] strs) {
   if (strs.length == 0) return "";
   String prefix = strs[0];
   for (int i = 1; i < strs.length; i++)
       while (strs[i].indexOf(prefix) != 0) {
           prefix = prefix.substring(0, prefix.length() - 1);
           if (prefix.isEmpty()) return "";
       }        
   return prefix;
}

1
2
3
4
5
6
7
8
9
10

首先，我们将描述一种查找一组字符串的最长公共前缀 $LCP(S_1 \ldots S_n)$ 的简单方法。

我们将会用到这样的结论： $LCP(S_1 \ldots S_n) = LCP(LCP(LCP(S_1, S_2),S_3),\ldots S_n)$ .

对于本题而言，采取如下算法：

依次遍历字符串 $[S_1 \ldots S_n]$ ，当遍历到第 $i$ 个字符串的时候，找到最长公共前缀 $LCP(S_1 \ldots S_i)$ 。当 $LCP(S_1 \ldots S_i)$ 是一个空串的时候，算法就结束了。否则，在执行了 $n$ 次遍历之后，算法就会返回最终答案 $LCP(S_1 \ldots S_n)$ 。

对应代码部分，使用样例1 的数据，首先假定 prefix 为 "flower"。检查第二个字符串，利用 indexOf 方法，该方法可以接收一个子字符串 s，如果父字符串中包含有该字符串，则子串在父串中第一次出现的位置，如果不存在子串则返回 -1。对应本题，如果有公共前缀则返回 0。第二个字符串为 flow ，经过 while 循环，prefix 的值更新为 “ flow ”。第三个字符串 “ flight ”，更新其值为 fl 后，for 循环结束，函数返回 “ fl ” 。

复杂度分析:

时间复杂度 : $O(S)$ $O (S)$ . S 是所有字符串中字符数量的总和。
- 最坏的情况下， $n$ 个字符串都是相同的。算法会将 $S_1$ 与其他字符串 $[S_2 \ldots S_n]$ 都做一次比较。这样就会进行 $S$ 次字符比较，其中 $S$ 是输入数据中所有字符数量。
空间复杂度 : $O( 1 )$ .

# 2.2 优化水平扫描法

📃帖子原址 (opens new window)

核心代码：

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    for (int i = 0; i < strs[0].length() ; i++){
        char c = strs[0].charAt(i);
        for (int j = 1; j < strs.length; j ++) {
            if (i == strs[j].length() || strs[j].charAt(i) != c)
                return strs[0].substring(0, i);             
        }
    }
    return strs[0];
}

1
2
3
4
5
6
7
8
9
10
11

每次去比较每个字符串的相同下标位置的字符是否相同，如果相同则比较下一个，如果存在不同，那么直接返回从下标 0 开始到不相同位置下标的 strs[0] 的字符串的子串。

需要注意的是，由于公共前缀的特殊性，假定第一个字符串为最长公共前缀是没问题的，同时可以带来处理的便利。

复杂度分析:

时间复杂度 : $O(S)$ $O (S)$ . S 是所有字符串中字符数量的总和。
- 最坏情况下，输入数据为 $n$ 个长度为 $m$ 的相同字符串，算法会进行 $S = m*n $ 次比较。可以看到最坏情况下，本算法的效率与算法一相同，但是最好的情况下，算法只需要进行 $n*minLen$ 次比较，其中 $minLen$ 是数组中最短字符串的长度。
空间复杂度 : $O( 1 )$ .

# 2.3 分治

📃帖子原址 (opens new window)

这个算法的思路来自于LCP操作的结合律。我们可以发现：

$LCP(S_1 \ldots S_n) = LCP(LCP(S_1 \ldots S_k), LCP (S_{k+1} \ldots S_n))$ ，其中 $LCP(S_1 \ldots S_n)$ 是字符串 $[S_1 \ldots S_n]$ 的最长公共前缀， $1 < k < n$ 。

为了应用上述的结论，我们使用分治的技巧，将原问题 $LCP(S_i\cdots S_j)$ 分成两个子问题 $LCP(S_i\cdots S_{mid})$ 与 $LCP(S_{mid+1}, S_j)$ ，其中 mid = $\frac{i+j}{2}$ 。我们用子问题的解 lcpLeft 与 lcpRight 构造原问题的解 $LCP(S_i \cdots S_j)$ 。从头到尾挨个比较 lcpLeft 与 lcpRight 中的字符，直到不能再匹配为止。计算所得的 lcpLeft 与 lcpRight 最长公共前缀就是原问题的解 $LCP(S_i\cdots S_j)$ 。

核心代码：

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";    
        return longestCommonPrefix(strs, 0 , strs.length - 1);
}

private String longestCommonPrefix(String[] strs, int l, int r) {
    if (l == r) {
        return strs[l];
    }
    else {
        int mid = (l + r)/2;
        String lcpLeft =   longestCommonPrefix(strs, l , mid);
        String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
        return commonPrefix(lcpLeft, lcpRight);
   }
}

String commonPrefix(String left,String right) {
    int min = Math.min(left.length(), right.length());       
    for (int i = 0; i < min; i++) {
        if ( left.charAt(i) != right.charAt(i) )
            return left.substring(0, i);
    }
    return left.substring(0, min);
}

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

复杂度分析

最坏情况下，我们有 $n$ 个长度为 $m$ 的相同字符串。

时间复杂度： $O(S)$ ， $S$ 是所有字符串中字符数量的总和， $S=m*n$ 。

时间复杂度的递推式为 $T(n)=2\cdot T(\frac{n}{2})+O(m)$ ，化简后可知其就是 $O(S)$ 。最好情况下，算法会进行 $minLen\cdot n$ 次比较，其中 $minLen$ 是数组中最短字符串的长度。
空间复杂度： $O(m \cdot log(n))$

内存开支主要是递归过程中使用的栈空间所消耗的。一共会进行 $log(n)$ 次递归，每次需要 $m$ 的空间存储返回结果，所以空间复杂度为 $O(m\cdot log(n))$ 。

2020-03-20

← 3.无重复字符的最长子串 19.删除链表的倒数第N个节点 →

# 14.Longest Common Prefix 最长公共前缀

# 1. 题目详情

# 2. 优秀解答：

# 2.1 水平扫描法

# 2.2 优化 水平扫描法

# 2.3 分治

# 2.2 优化水平扫描法