14、最长公共前缀

鲁迅曾说，每天刷一道二哥的 LeetCode 笔记，不但身体健康，而且精神抖擞。

题意

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

""。

难度

简单

示例

输入：strs = ["flower","flow","flight"]

输出："fl"

输入：strs = ["dog","racecar","car"]

输出：""

解释：输入不存在公共前缀。

分析

这道题最重要的是，搞清楚什么是公共前缀。公共前缀就是字符串数组中，所有字符串都

包含的前缀。例如，字符串数组 ["flower","flow","flight"] 的最长公共前缀就是 fl。

一个很容易想到的办法，我们将数组中的第一个字符串作为初始的最长公共前缀，然后逐

个将它与数组中的其他字符串进行比较。在比较的过程中，我们逐步缩短这个公共前缀，

直到它同时是所有字符串的前缀。

①、初始前缀：假设整个数组的最长公共前缀就是数组中的第一个字符串，即 prefix =

strs[0]。

②、遍历字符串数组：遍历字符串数组中的每一个字符串。对于每个字符串 strs[i]，我们

检查它是否包含当前的最长公共前缀 prefix。（可以跳过第一个，因为第一个就是它自

己）

③、更新前缀：

• 如果当前字符串 strs[i] 包含前缀 prefix，我们就继续下一个字符串的比较。

• 如果当前字符串 strs[i] 不包含前缀 prefix，我们就缩短前缀的长度，即 prefix =

prefix.substring(0, prefix.length() - 1)，然后再次检查。

• 重复这个过程，直到 strs[i] 包含了 prefix 或 prefix 变成空字符串（即没有公共前

缀）。

④、返回结果：最终 prefix 就是数组中所有字符串的最长公共前缀。

我们来看题解：

public class Solution {

public String longestCommonPrefix(String[] strs) {

if (strs == null || 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;

}

}

假设输入的字符串数组是 ["flower","flow","flight"]。

1. 初始 prefix = "flower"。

2. 比较 prefix 和 "flow"，发现 "flow" 不包含 "flower"，开始逐渐缩短 prefix：

– prefix = "flowe"，"flow" 仍不包含 "flowe"。

– prefix = "flow"，"flow" 包含 "flow"。

3. 比较 prefix 和 "flight"，发现 "flight" 不包含 "flow"，开始逐渐缩短 prefix：

– prefix = "flo"，"flight" 仍不包含 "flo"。

– prefix = "fl"，"flight" 包含 "fl"。

4. 返回结果 prefix = "fl"。

来看一下题解效率：

014.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%89%8D%E7%BC%80-

20240123182612.png

还不错，beat 了 100% 的用户。

总结

这道题的关键是，搞清楚什么是公共前缀。公共前缀就是字符串数组中，所有字符串都包

含的前缀。

巧妙的点是，我们可以字符串数组的第一个字符串作为初始的最长公共前缀，然后逐个将

它与数组中的其他字符串进行比较。在比较的过程中，我们逐步缩短这个公共前缀，直到

它同时是所有字符串的前缀。

大家可以感受一下这个过程，所用到的基础知识无外乎：

• 字符串的 indexOf() 方法，用于判断一个字符串是否包含另一个字符串。这样就可以

判断当前字符串是否包含当前最长公共前缀。

• 字符串的 substring() 方法，用于截取字符串的子串。这样就可以缩短当前最长公共

前缀。

• 字符串的 isEmpty() 方法，用于判断字符串是否为空。为空说明就没有公共前缀了。

剩下的就是 for 循环和 while 循环了，for 循环用于遍历字符串数组，while 循环用于缩短

当前最长公共前缀。

这些知识大家可以通过二哥的 Java 进阶之路来学习。

• 流程控制语句

• 字符串

力扣链接：https://leetcode.cn/problems/longest-common-prefix/