标签#

• 平台：LeetCode
• 难度：简单
• 数据结构：字符串
• 算法：字符串匹配
• 解题模式：区间收缩

一、题目概述#

给定一个字符串数组，找出其中所有字符串共有的最长前缀。如果不存在公共前缀，则返回空字符串。当前实现对 null 数组、空数组以及包含 null 元素的数组统一返回空字符串。

二、解题思路#

先把数组中的第一个字符串作为候选公共前缀，再依次与后续字符串比较。每轮只比较候选前缀和当前字符串开头连续相同的字符，并把候选前缀缩短到本轮得到的公共长度。

候选前缀只会保持不变或变短，不可能重新增长。当某轮公共长度为 0 时，后续字符串也不可能恢复公共前缀，因此可以直接返回空字符串。

三、执行过程#

以 ["flower", "flow", "flight"] 为例：

1. 初始候选前缀为 flower。
2. 与 flow 比较，前 4 个字符相同，候选前缀缩短为 flow。
3. 与 flight 比较，前 2 个字符相同，候选前缀缩短为 fl。
4. 所有字符串比较完成，返回 fl。

四、代码实现#

1
public class LeetCode0014LongestCommonPrefix {
2

3
    public String longestCommonPrefix(String[] strings) {
4
        if (strings == null || strings.length == 0) {
5
            return "";
6
        }
7

8
        String prefix = strings[0];
9
        if (prefix == null) {
10
            return "";
11
        }
12

13
        for (int i = 1; i < strings.length; i++) {
14
            String current = strings[i];
15
            if (current == null) {
16
                return "";
17
            }
18

19
            int commonLength = 0;
20
            int maxCommonLength = Math.min(prefix.length(), current.length());
21
            while (commonLength < maxCommonLength
22
                    && prefix.charAt(commonLength) == current.charAt(commonLength)) {
23
                commonLength++;
24
            }
25

26
            if (commonLength == 0) {
27
                return "";
28
            }
29
            prefix = prefix.substring(0, commonLength);
30
        }
31

32
        return prefix;
33
    }
34
}

五、关键代码说明#

• prefix：保存截至当前字符串为止的公共前缀。
• maxCommonLength：比较长度不能超过候选前缀和当前字符串中较短者，避免下标越界。
• commonLength：记录两个字符串从开头起连续相同的字符数量。
• prefix.substring(0, commonLength)：按本轮结果收缩候选前缀。
• commonLength == 0：说明公共前缀已经不存在，可以提前结束。

六、复杂度分析#

• 时间复杂度：O(S)，其中 S 是输入字符串的字符总数；每轮比较不会超过当前字符串长度和候选前缀长度。
• 空间复杂度：O(L)，其中 L 是第一个字符串的长度；Java 17 的 substring 会创建新字符串，候选前缀不会超过第一个字符串。

七、注意事项#

• 每次比较的上限必须取两个字符串长度的较小值，否则可能发生下标越界。
• 数组中出现空字符串时，公共前缀必然为空。
• 当前实现明确把 null 数组或 null 元素作为无公共前缀处理。
• 单元素数组不进入循环，直接返回该元素本身。

八、面试知识点：公共前缀的逐步收缩#

这道题的核心是公共前缀具有单调性：加入更多字符串后，公共前缀只可能变短，不可能变长。因此可以维护一个候选前缀，并让它与每个新字符串求公共前缀。

常见追问是为什么可以在公共长度变成 0 时提前返回。因为空字符串已经是当前所有已处理字符串的最长公共前缀，后续再加入字符串只能保持为空，无法产生新的非空公共前缀。

另一种常见写法是按列纵向扫描，即固定字符下标并检查所有字符串的同一位置。两种写法的最坏时间复杂度相同；当前实现按字符串逐个比较，更直接地体现了候选前缀不断收缩的过程。

回到本题，面试时可以这样回答：先把第一个字符串作为候选前缀，依次和其他字符串从头比较，得到相同字符长度后截短候选前缀。如果某轮没有任何相同字符就提前返回空字符串。最终候选前缀就是答案，时间复杂度为 O(S)，其中 S 是输入字符串的字符总数。