题目链接
https://leetcode-cn.com/problems/longest-common-prefix/
题目描述
编写一个函数来查找字符串数组中的最长公共前缀,如果不存在公共前缀,返回空字符串 ""
。
示例
示例 1:
输入:
strs = ["flower", "flow", "flight"]
输出:"fl"
示例 2:
输入:
strs = ["dog", "racecar", "car"]
输出:""
解释: 输入不存在公共前缀。
题解
横向扫描
横向比较的思路就是我们每次传入两个字符串对比,得到这两项的公共前缀,再拿得到的结果和下一个字符串对比,直到所有字符串都对比完得到最大公共前缀。
$LCP(S_1…S_n) = LCP(LCP(LCP(LCP(S_1, S_2), S_3), S_4), …S_n)$

根据示意图可以知道,我们首先应该用一个变量存储 LCP
过程的结果,默认为字符串数组的第一项,并遍历字符串数组,用当前的公共前缀去和每一项字符串对比得出新的公共前缀。
在获取两个字符串公共前缀的过程中需要遍历字符串,所以当遍历次数达到较短的字符串长度时,或者出现某次遍历字符串对应位置上两个字符不相等时,则可以停止遍历得出当前的公共前缀,当所字符串数组遍历完可以得出最终的公共前缀并返回。
const longestCommonPrefix = (strs) => {
if (strs.length === 0) return '';
const lcp = (str1, str2) => {
const length = Math.min(str1.length, str2.length);
let index = 0;
while (index < length && str1[index] === str2[index]) {
index++;
}
return str1.slice(0, index);
}
return strs.reduce((prev, next) => lcp(prev, next));
}
复杂度分析:
- 时间复杂度:
n
为字符串数组的规模,m
为lcp
函数遍历的平均次数,故为 $O(m * n)$ - 空间复杂度:$O(1)$
纵向扫描
相比于横向扫描,整个字符串为维度两两求公共前缀,纵向扫描是以每一个字符为维度的遍历,最后得到公共前缀,我们也可以把字符串的看做一个不规则的表格,每个字符代表一个单元格。

在每次一个字符一个字符的比对时,当有内层遍历一个字符串对应位置的字符与其他不符合,或者外层遍历到最短的那个字符串时结束。
const longestCommonPrefix = (strs) => {
if (strs.length === 0) return '';
const len = strs.length;
const count = strs[0].length;
for (let i = 0; i < count; i++) {
for (let j = 0; j < len; j++) {
if (i === strs[j].length || strs[0][i] !== strs[j][i]) {
return strs[0].slice(0, i);
}
}
}
return strs[0];
}
复杂度分析:
- 时间复杂度:
n
为字符串数组的规模,m
字符串的平均长度,故为 $O(m * n)$ - 空间复杂度:$O(1)$
分治策略
分治算法满足的条件:
- 分解:将要解决的问题划分成规模更小的问题;
- 求解:将划分的足够小的子问题用相对简单的方法解决;
- 合并:按照原问题的要求将子问题的解逐层合并为原问题的解。
通过横向扫描法我们可以知道两个字符串可以求解公共前缀,$n = 2$ 这个规模就是我们要求解的子问题,而通过结合律有以下结论:

每一个大问题都可以通过求解的中间值 mid
范围划分为两个子问题 $LCP(S_1…S_mid)$ 和 $LCP(S_{mid + 1}…S_n)$,子问题继续划分为两个子问题,依次类推,划分到最小颗粒度为止(范围内不大于两个字符串求解),再通过子问题得到的结果逐级合并,所以使用递归回溯更适合解决分治的问题。
const longestCommonPrefix = (strs) => {
if (strs.length === 0) return '';
const commonPrefix = (lcpLeft, lcpRight) => {
const len = Math.min(lcpLeft.length, lcpRight.length);
for (let i = 0; i < len; i++) {
if (lcpLeft[i] !== lcpRight[i]) {
return lcpLeft.slice(0, i);
}
}
return lcpLeft.slice(0, len);
}
const lcp = (start, end) => {
if (start === end) return strs[start];
const mid = Math.floor((start + end) / 2);
return commonPrefix(lcp(start, mid), lcp(mid + 1, end));
}
return lcp(0, strs.length - 1);
}
复杂度分析:
- 时间复杂度:通过分治策略的递推公式 $T(n) = k * T(n / k) + O(n - 1)$
- 其中每个问题每次分治的子问题数为
2
- 分治 $logn$ 次得:
- 推导得:$T(n) = n * T(1) + O(n - 1) = O(n) + O(n - 1) = O(n)$
- 因每次子问题执行复杂度为 $O(m)$,
m
为字符串平均长度,最终可推出时间复杂度为 $O(m * n)$
- 其中每个问题每次分治的子问题数为
- 空间复杂度:主要取决于递归调用的次数,故为 $O(logn)$
二分查找
寻找最大公共前缀的过程中有一点在其他的实现方式中也有应用,就是最大前缀的长度一定不会超过最短的字符串的长度,那是不是可以高效的在 $[0, minLength]$ 范围中尝试寻找最大前缀长度的范围?
我们粗略的把最短的字符串不断的分成两个范围,一个是已经确定是公共前缀的范围,一个是未确定公共前缀的范围,然后不断的去在未确定公共前缀的范围中寻找边界,不断的缩短未知的范围直到找到最大公共前缀。

此时我们就可以通过二分查找法来实现,设置变量 low
和 high
指向未知范围的起点和终点,通过起点终点求出中间点 mid
,此时两个范围 $[low, mid)$ 和 $[mid, high)$
- 被确定为公共前缀,则让
low
指定到mid
所在的位置缩小未知范围; - 被确定不是公共前缀,则让
high
指定到mid - 1
的位置缩小未知范围; - 直到
low
和hight
重叠或相交,数组中任何一个字符串的 $[0, low)$ 就是最大公共前缀。
const longestCommonPrefix = (strs) => {
if (strs.length === 0) return '';
const isCommonPrefix = (strs, len) => {
const [first, ...other] = strs;
return other.every((str) => first.slice(0, len) === str.slice(0, len));
}
let low = 0;
let high = strs.reduce((min, str) => Math.min(min, str.length), Infinity);
while (low < high) {
const mid = Math.ceil((low + high) / 2);
if (isCommonPrefix(strs, mid)) {
low = mid;
} else {
high = mid - 1;
}
}
return strs[0].slice(0, low);
}
复杂度分析:
- 时间复杂度:
n
为字符串数组的规模,m
字符串的平均长度,二分查找迭代次数为 $O(logm)$,每次判断是否是公共前缀需要执行 $O(m * n)$ 次,故为 $O(mnlogm)$ - 空间复杂度:$O(1)$