LeetCode 每日一题:Longest Common Prefix(最长公共前缀)的二分与 Trie 双解法剖析

原创2026-09-17 16:11:411,438 阅读
文章标签:教程教育文档

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:trie binary 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.

从示例可以看出两个关键特征:

  1. 公共前缀必须对所有字符串成立。["flower","flow","flight"] 中三个字符串前两个字符均为 "fl",因此答案为 "fl"。
  2. 无公共前缀时返回空串。["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);
};

逐步拆解

  1. 空数组与单元素处理:strs.length === 0 直接返回 "";strs.length === 1 时唯一字符串本身即最长公共前缀,直接返回 strs[0]。这两行边界处理省去了后续循环中的空指针风险。
  2. 求最短长度:遍历所有字符串,用 Math.min 维护 minLen,它是二分搜索的上界。
  3. 二分搜索:low = 0,high = minLen,循环条件 low <= high;middle = (low + high) >> 1 使用位运算右移实现向下取整除法(等价于 Math.floor((low + high) / 2)),这是 JavaScript 中常见的快速写法。
  4. 单调性判定:isCommonPrefix(strs, middle) 以第一个字符串的前 middle 个字符为基准,逐一用 startsWith(prefix) 检查其余字符串;全部通过则说明答案至少为 middle,收缩左边界 low = middle + 1;否则收缩右边界 high = middle - 1。
  5. 收尾:循环结束时 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 前缀树节点结构与单词插入路径示意图

如上图所示,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 应用于本题的思路在原文档中概括为两步:

  1. 建立 Trie:把 strs 中所有字符串依次插入前缀树。
  2. 从根向下遍历:只要当前节点只有一个孩子(所有字符串仍共享同一前缀),就继续深入;一旦出现某个节点拥有超过一个子元素(字符串在此分叉),或遇到单词结束标记,公共前缀到此为止。

对 ["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 的空间开销会被摊薄,成为更优解。

延伸阅读

登录后查看全文
leetcode