最长公共前缀怎么求？四种解法一次讲清
求一组字符串的最长公共前缀，是 LeetCode 第 14 题。
题目很短：给你一个字符串数组，找出它们共有的最长前缀；没有就返回空字符串。
我第一次做的时候随手写了个横向扫描，过了，但总觉得不踏实。
后来翻官方题解才发现，这道题至少有四种思路，复杂度还各有讲究。
下面把它们一次讲清楚，代码用 Go，都能直接跑。
最长公共前缀是什么？
最长公共前缀指一组字符串从第一个字符开始，连续相同的最长那一段。
举个例子。
数组 ["flower", "flow", "flight"]，公共前缀是 fl。
数组 ["dog", "cat", "fish"]，第一个字符就对不上，结果是空串。
只要有任意一个字符串提前结束，或者某一位字符不一致，前缀就到此为止。
横向扫描：最直觉的写法
横向扫描的思路是：先拿第一个字符串当候选前缀，再依次和后面每个字符串求公共前缀。
公式上就是 LCP(S1…Sn) = LCP(LCP(LCP(S1, S2), S3), …Sn)。
每比较一次，候选前缀只会变短或不变。
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
prefix := strs[0]
for i := 1; i < len(strs); i++ {
prefix = commonPrefix(prefix, strs[i])
if prefix == "" {
return "" // 提前剪枝，没必要再比了
}
}
return prefix
}
// 求两个字符串的公共前缀
func commonPrefix(s1, s2 string) string {
n := min(len(s1), len(s2))
i := 0
for i < n && s1[i] == s2[i] {
i++
}
return s1[:i]
}时间复杂度 O(mn)，m 是字符串平均长度，n 是字符串个数。
空间复杂度 O(1)。
注意那个 prefix == "" 的提前返回，我一开始漏写，遇到第一位就不匹配的数据还在傻傻往后跑。
纵向扫描：按列比对
纵向扫描换了个角度：不再两两比，而是按字符位置一列一列地比。
先看所有字符串的第 0 位是否相同，再看第 1 位，直到某一位出现分歧或某个串走到头。
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
for i := 0; i < len(strs[0]); i++ {
c := strs[0][i]
for j := 1; j < len(strs); j++ {
// 走到某个串末尾，或字符不一致
if i == len(strs[j]) || strs[j][i] != c {
return strs[0][:i]
}
}
}
return strs[0]
}复杂度和横向扫描一样，O(mn) 时间，O(1) 空间。
区别在于纵向扫描遇到分歧能立刻停，最坏情况下比较次数往往更少。
分治：把问题切两半
分治的核心想法是把数组从中间切开，分别求左右两半的公共前缀，再合并。
LCP(S1…Sn) = LCP(LCP(S1…Sk), LCP(Sk+1…Sn))。
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
return lcp(strs, 0, len(strs)-1)
}
func lcp(strs []string, lo, hi int) string {
if lo == hi {
return strs[lo]
}
mid := (lo + hi) / 2
left := lcp(strs, lo, mid)
right := lcp(strs, mid+1, hi)
return commonPrefix(left, right)
}时间复杂度还是 O(mn)，但因为递归用了栈，空间是 O(m log n)。
说白了，分治在这道题上并不省时间，更多是练手思路。
二分查找：在前缀长度上二分
这个解法稍微绕一点。
公共前缀的长度，一定不超过最短字符串的长度。
那就在 [0, 最短长度] 这个区间里二分：如果长度 mid 的前缀是公共的，就往更长找；否则往更短找。
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
minLen := len(strs[0])
for _, s := range strs {
if len(s) < minLen {
minLen = len(s)
}
}
low, high := 0, minLen
for low < high {
mid := (low + high + 1) / 2
if isCommonPrefix(strs, mid) {
low = mid
} else {
high = mid - 1
}
}
return strs[0][:low]
}
func isCommonPrefix(strs []string, length int) bool {
prefix := strs[0][:length]
for i := 1; i < len(strs); i++ {
if !strings.HasPrefix(strs[i], prefix) {
return false
}
}
return true
}时间复杂度 O(mn log m)，空间 O(1)。
理论上它比前面几种多了个 log m，实战里反而不一定快。
四种解法复杂度对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 横向扫描 | O(mn) | O(1) | 最直觉，可提前剪枝 |
| 纵向扫描 | O(mn) | O(1) | 遇分歧即停，常更快 |
| 分治 | O(mn) | O(m log n) | 练递归思路 |
| 二分查找 | O(mn log m) | O(1) | 思路新颖，实战未必快 |
n 是字符串个数，m 是字符串平均长度。
面试里写横向或纵向扫描就够了，干净利落。
分治和二分更多是展示你知道这些套路。
一个容易忽略的坑
上面所有代码都是按字节（byte）比较的。
LeetCode 第 14 题限定输入是小写英文字母，所以没问题。
但如果输入含中文或 emoji，按字节切 s[:i] 可能切碎一个多字节字符，得到乱码。
真要处理 Unicode，得先 []rune(s) 转成 rune 切片再比。
这点我也是被一道变体题坑过才记住的。
常见问题
数组里有空字符串会怎样？
只要任意一个字符串是空串，最长公共前缀必然是空串。
横向和纵向扫描天然能处理：第一轮比较就会返回空。
横向扫描和纵向扫描哪个更好？
两者复杂度相同，都是 O(mn)。
纵向扫描遇到不匹配能立刻停在当前列，平均比较次数通常更少，略占优。
二分查找复杂度更高，为什么还要学？
它提供了一种「在答案空间上二分」的思路。
这类思想在很多查找最优值的题里都用得上，本题只是个入门练习。
这道题需要排序吗？
不需要。
公共前缀和顺序无关，排序只会徒增 O(n log n) 的开销。
如果大家对某种解法还有疑问，或者踩过别的坑，欢迎在评论区交流～～～
参考：LeetCode 官方题解 最长公共前缀
版权声明
未经授权，禁止转载本文章。
如需转载请保留原文链接并注明出处。即视为默认获得授权。
未保留原文链接未注明出处或删除链接将视为侵权，必追究法律责任！
本文原文链接： https://fiveyoboy.com/articles/longest-common-prefix/
备用原文链接： https://blog.fiveyoboy.com/articles/longest-common-prefix/