LeetCode 每日一题:Longest Common Prefix(最长公共前缀)的二分与 Trie 双解法剖析
LeetCode 每日一题:Longest Common Prefix(最长公共前缀)的二分与 Trie 双解法剖析
本篇技术指南以 leetcode 仓库每日一题系列中的 2019-06-03 每日一题 为骨架,围绕 LeetCode 第 14 题 Longest Common Prefix(最长公共前缀)展开,完整讲解二分法、Trie(前缀树)与暴力法三种解法的思路、代码与复杂度,并结合仓库中的 Trie 前缀树专题 与 208. 实现 Trie (前缀树) 题解 做源码级印证。读完本文,你将掌握最长公共前缀问题的标准解法范式,理解二分答案如何套用于字符串前缀判定,以及前缀树如何用空间换时间优化前缀类问题。
题目信息卡片
- 时间:2019-06-03
- 题目:Longest Common Prefix(最长公共前缀)
- tag:
triebinary search
这道题是 leetcode 仓库 每日一题 活动的第一期题目。每日一题是作者在交流群(微信与 QQ)中发起的一种活动:大家一起解同一道题,讨论更集中、反馈更多,题目会被记录下来并沉淀进仓库的题解模块。本期题解收录于 daily/2019-06-03.md,最终的可运行答案文件保存在 daily/answers/14.longest-common-prefix.js。
题目描述与示例分析
原题要求编写一个函数,在字符串数组中找到所有字符串的最长公共前缀;如果不存在公共前缀,返回空字符串 ""。
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Example 1:
Input: ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:
All given inputs are in lowercase letters a-z.
从示例可以看出两个关键特征:
- 公共前缀必须对所有字符串成立。
["flower","flow","flight"]中三个字符串前两个字符均为"fl",因此答案为"fl"。 - 无公共前缀时返回空串。
["dog","racecar","car"]首字符d、r、c各不相同,公共前缀长度为 0,返回""。
题目约束所有输入均为小写字母 a-z,这使得基于字符索引的 Trie 实现可以简化为固定大小(26)的子节点数组;同时字符串可能为空数组或单个元素,这些边界情况必须在代码中显式处理。
解法一:二分法(Binary Search)
思路推导
公共前缀长度一定不会超过数组中最短字符串的长度,记其为 minLen。于是候选答案长度被限制在区间 [0, minLen] 内,问题转化为:
在
[0, minLen]中寻找最大的k,使得所有字符串的前k个字符都相等。
这个判定函数 isCommonPrefix(strs, middle) 具有单调性:如果长度为 k 的前缀是公共前缀,那么任何更短的长度也必然是公共前缀;反之如果长度为 k 不是,则任何更长的长度也不是。因此可以直接套用二分查找模板,这正是 tag 中标 binary search 的原因。
参考代码
仓库 daily/answers/14.longest-common-prefix.js 中保存了完整实现(与 daily/2019-06-03.md 中参考答案一致):
function isCommonPrefix(strs, middle) {
const prefix = strs[0].substring(0, middle);
for (let i = 1; i < strs.length; i++) {
if (!strs[i].startsWith(prefix)) return false;
}
return true;
}
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
// trie 解法
// 时间复杂度O(m) 空间复杂度O(m * n)
// tag: 二分法
// 时间复杂度 O(n*logm) 空间复杂度O(1)
if (strs.length === 0) return "";
if (strs.length === 1) return strs[0];
let minLen = Number.MAX_VALUE;
for (let i = 0; i < strs.length; i++) {
minLen = Math.min(minLen, strs[i].length);
}
let low = 0;
let high = minLen;
while (low <= high) {
const middle = (low + high) >> 1;
if (isCommonPrefix(strs, middle)) low = middle + 1;
else high = middle - 1;
}
return strs[0].substring(0, (low + high) >> 1);
};
逐步拆解
- 空数组与单元素处理:
strs.length === 0直接返回"";strs.length === 1时唯一字符串本身即最长公共前缀,直接返回strs[0]。这两行边界处理省去了后续循环中的空指针风险。 - 求最短长度:遍历所有字符串,用
Math.min维护minLen,它是二分搜索的上界。 - 二分搜索:
low = 0,high = minLen,循环条件low <= high;middle = (low + high) >> 1使用位运算右移实现向下取整除法(等价于Math.floor((low + high) / 2)),这是 JavaScript 中常见的快速写法。 - 单调性判定:
isCommonPrefix(strs, middle)以第一个字符串的前middle个字符为基准,逐一用startsWith(prefix)检查其余字符串;全部通过则说明答案至少为middle,收缩左边界low = middle + 1;否则收缩右边界high = middle - 1。 - 收尾:循环结束时
low是第一个"失败"的长度,(low + high) >> 1即最大的可行公共前缀长度,用它截取strs[0]作为最终答案。
复杂度分析
- 时间复杂度 O(n·log m):
n为字符串个数,m为最短字符串长度。二分过程迭代O(log m)轮,每轮isCommonPrefix最坏比较O(n)个字符串。 - 空间复杂度 O(1):除常量变量外,只通过
substring临时生成前缀,未使用与输入规模相关的额外空间。
对照仓库 daily/2019-06-03.md 中注释的标注:二分法时间复杂度 O(n·log m)、空间复杂度 O(1),两者完全一致。
解法二:Trie(前缀树 / 字典树)
Trie 的核心思想
二分法把字符串判定抽象成数值二分,而 Trie 解法则是从"前缀"这一数据结构本质出发。Trie 也叫字典树、前缀树,是一棵多叉树:根节点无实际意义,每个非根节点存储一个字符,并附带控制信息(如 isWord 标记是否为单词结尾)。其核心操作是插入与查询,删除很少使用。关于 Trie 的完整理论(节点结构、插入、查询、模板与复杂度),可参考仓库 thinkings/trie.md 专题。
Trie 的核心优势是空间换时间:把公共前缀只存储一次,从而在大量字符串共享前缀时显著降低查询开销。原文档特别指出,本题的 Trie 解法可以借鉴 LeetCode 第 208 题 Implement Trie (Prefix Tree) 的实现,仓库中已有完整题解 problems/208.implement-trie-prefix-tree.md。
如上图所示,Trie 中每个节点代表一个字符,节点上的 isWord 标记该字符是否是某个单词的结尾;插入单词时从根出发逐字符寻找或创建节点,蓝色箭头即单词的插入路径。
Trie 节点与三个核心 API
仓库 problems/208.implement-trie-prefix-tree.md 中给出了 208 题的完整实现。由于题目约束字符仅为 a-z,子节点可用数组按下标存取,通过 computeIndex 把字符映射到 0~25 的索引:
function TrieNode(val) {
this.val = val;
this.children = [];
this.isWord = false;
}
function computeIndex(c) {
return c.charCodeAt(0) - "a".charCodeAt(0);
}
三个核心 API 的逻辑都是从根出发逐字符定位节点:
- insert(word):逐字符查找子节点,不存在则创建;走到末尾后置
ws.isWord = true标记单词结束。 - search(word):逐字符查找,中途缺失返回
false;走完后返回ws.isWord,以区分"单词存在"与"仅是某单词的前缀"。 - startsWith(prefix):与
search类似,但只关心前缀路径是否存在,走完即返回true,无需检查isWord。
用 Trie 求解最长公共前缀
将 Trie 应用于本题的思路在原文档中概括为两步:
- 建立 Trie:把
strs中所有字符串依次插入前缀树。 - 从根向下遍历:只要当前节点只有一个孩子(所有字符串仍共享同一前缀),就继续深入;一旦出现某个节点拥有超过一个子元素(字符串在此分叉),或遇到单词结束标记,公共前缀到此为止。
对 ["flower","flow","flight"] 建树后,根节点只有 f 一个孩子,f 之后只有 l,l 之后 o、i 分叉,因此最长公共前缀为 "fl"。对 ["dog","racecar","car"],根节点就有 d、r、c 三个孩子,直接返回 ""。
原文档注释中给出的复杂度标注为:Trie 解法时间复杂度 O(m)、空间复杂度 O(m·n),其中 m 为字符串长度、n 为字符串个数——这里的 O(m) 可理解为建立 Trie 后从根到第一个分叉节点的路径长度即为答案,建树与遍历整体开销由插入所有字符决定。这一"用空间换时间"的特点与 thinkings/trie.md 中"前缀树的意义实际上是空间换时间,利用字符串的公共前缀来降低查询的时间开销"的论述完全吻合。
原文档中 Trie 参考代码即 problems/208.implement-trie-prefix-tree.md 中的完整 Trie 类(insert / search / startsWith 三个方法),本题的具体解法(建立 Trie 后逐层统计孩子数)文档留作读者自行补充完善,这里不再重复粘贴,读者可直接结合上文 API 说明实现。
解法三:暴力法(逐字符 / 逐串扫描)
原文档对暴力法仅作一句提示:"比较常规的一种解法,大部分人采用的做法,这里就不再赘述"。这里简要展开以保持题解完整性:
- 纵向扫描(逐字符比对):取第一个字符串,依次比较每个字符是否在其余所有字符串的相同位置出现,一旦出现不同或某字符串已到末尾即停止。时间复杂度 O(S),S 为所有字符串字符总数,空间 O(1)。
- 横向扫描(逐串求前缀):先以第一个字符串为基准,依次与后续每个字符串求公共前缀并更新基准,最终基准即为答案。
暴力法实现直观、边界容易处理,但不具备二分法的对数级收敛优势,也不像 Trie 那样能复用前缀结构;在字符串数量多、长度长时性能劣于前两种解法,这也是本题 tag 只标 trie 与 binary search 的原因。
三种解法复杂度对比与选型建议
| 解法 | 核心思路 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
| 二分法 | 对前缀长度做二分,配合 startsWith 单调判定 |
O(n·log m) | O(1) | 面试首选,实现简洁、无额外空间 |
| Trie | 建前缀树后沿单分支路径求公共前缀 | 建树 + 遍历,整体 O(m·n)(原文档标注 O(m) / O(m·n)) | O(m·n) | 前缀类问题通用解法,可复用于 208/211/212 等题 |
| 暴力法 | 纵向或横向逐字符扫描 | O(S)(S 为总字符数) | O(1) | 代码最直观,适合快速 AC |
选型建议:日常笔试面试中二分法以"低空间 + 对数级时间"胜出;若题目同时涉及前缀查询、模糊匹配等多重操作,或可复用同一棵 Trie 处理多个查询,则 Trie 的空间开销会被摊薄,成为更优解。
延伸阅读
- 本题所在系列的完整索引:daily/README.md
- 本题可运行的答案文件:daily/answers/14.longest-common-prefix.js
- Trie 前缀树完整专题(节点设计、插入/查询/前缀查询、多语言模板):thinkings/trie.md
-
- 实现 Trie (前缀树) 详细题解:problems/208.implement-trie-prefix-tree.md
- 同属 Trie 专题的后续题目可参考:211.add-and-search-word-data-structure-design、212.word-search-ii
