LeetCode Hot100（39/100）——208. 实现 Trie (前缀树)

文章目录

• • 一、题目描述
  • 二、问题分析
  • • Trie 结构示意图
  • 三、设计思路
  • • 节点结构（TrieNode）
    • Trie 的核心操作流程
    • • 1. 插入单词 insert(word)
      • 2. 查找单词 search(word)
      • 3. 前缀匹配 startsWith(prefix)
  • 四、复杂度分析
  • 五、Java 实现代码
  • 六、运行示意图（时序图）
  • 七、优化与扩展

✅ 题目链接：LeetCode – Implement Trie (Prefix Tree) 难度：中等 适合人群：掌握数据结构基础、希望理解字符串搜索机制的开发者

一、题目描述

实现一个 前缀树（Trie），支持以下三种操作：

示例输入与输出：

输入：
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true

二、问题分析

Trie 是一种用于 高效存储和查找字符串集合 的数据结构。 它的核心思想是将字符串以「公共前缀」的方式组织在一棵树中，避免重复存储。

Trie 结构示意图

#mermaid-svg-ruFOIEgTxqL9gfJe{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-ruFOIEgTxqL9gfJe .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-ruFOIEgTxqL9gfJe .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-ruFOIEgTxqL9gfJe .error-icon{fill:#552222;}#mermaid-svg-ruFOIEgTxqL9gfJe .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ruFOIEgTxqL9gfJe .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-ruFOIEgTxqL9gfJe .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ruFOIEgTxqL9gfJe .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ruFOIEgTxqL9gfJe .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-ruFOIEgTxqL9gfJe .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ruFOIEgTxqL9gfJe .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ruFOIEgTxqL9gfJe .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ruFOIEgTxqL9gfJe .marker.cross{stroke:#333333;}#mermaid-svg-ruFOIEgTxqL9gfJe svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ruFOIEgTxqL9gfJe p{margin:0;}#mermaid-svg-ruFOIEgTxqL9gfJe .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-ruFOIEgTxqL9gfJe .cluster-label text{fill:#333;}#mermaid-svg-ruFOIEgTxqL9gfJe .cluster-label span{color:#333;}#mermaid-svg-ruFOIEgTxqL9gfJe .cluster-label span p{background-color:transparent;}#mermaid-svg-ruFOIEgTxqL9gfJe .label text,#mermaid-svg-ruFOIEgTxqL9gfJe span{fill:#333;color:#333;}#mermaid-svg-ruFOIEgTxqL9gfJe .node rect,#mermaid-svg-ruFOIEgTxqL9gfJe .node circle,#mermaid-svg-ruFOIEgTxqL9gfJe .node ellipse,#mermaid-svg-ruFOIEgTxqL9gfJe .node polygon,#mermaid-svg-ruFOIEgTxqL9gfJe .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-ruFOIEgTxqL9gfJe .rough-node .label text,#mermaid-svg-ruFOIEgTxqL9gfJe .node .label text,#mermaid-svg-ruFOIEgTxqL9gfJe .image-shape .label,#mermaid-svg-ruFOIEgTxqL9gfJe .icon-shape .label{text-anchor:middle;}#mermaid-svg-ruFOIEgTxqL9gfJe .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-ruFOIEgTxqL9gfJe .rough-node .label,#mermaid-svg-ruFOIEgTxqL9gfJe .node .label,#mermaid-svg-ruFOIEgTxqL9gfJe .image-shape .label,#mermaid-svg-ruFOIEgTxqL9gfJe .icon-shape .label{text-align:center;}#mermaid-svg-ruFOIEgTxqL9gfJe .node.clickable{cursor:pointer;}#mermaid-svg-ruFOIEgTxqL9gfJe .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-ruFOIEgTxqL9gfJe .arrowheadPath{fill:#333333;}#mermaid-svg-ruFOIEgTxqL9gfJe .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-ruFOIEgTxqL9gfJe .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-ruFOIEgTxqL9gfJe .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-ruFOIEgTxqL9gfJe .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-ruFOIEgTxqL9gfJe .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-ruFOIEgTxqL9gfJe .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-ruFOIEgTxqL9gfJe .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-ruFOIEgTxqL9gfJe .cluster text{fill:#333;}#mermaid-svg-ruFOIEgTxqL9gfJe .cluster span{color:#333;}#mermaid-svg-ruFOIEgTxqL9gfJe div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ruFOIEgTxqL9gfJe .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-ruFOIEgTxqL9gfJe rect.text{fill:none;stroke-width:0;}#mermaid-svg-ruFOIEgTxqL9gfJe .icon-shape,#mermaid-svg-ruFOIEgTxqL9gfJe .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-ruFOIEgTxqL9gfJe .icon-shape p,#mermaid-svg-ruFOIEgTxqL9gfJe .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-ruFOIEgTxqL9gfJe .icon-shape rect,#mermaid-svg-ruFOIEgTxqL9gfJe .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-ruFOIEgTxqL9gfJe .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-ruFOIEgTxqL9gfJe .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-ruFOIEgTxqL9gfJe :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

Root

a

p

l

e

b

t

在上图中，我们插入了 "apple"、"app"、"bat" 三个单词。 可见 "app" 是 "apple" 的前缀，两者共享节点，从而节省存储空间。

三、设计思路

节点结构（TrieNode）

• 每个节点包含：
  • children：保存连接到下一个字符的节点（通常用数组或哈希表）。
  • isEnd：标记当前节点是否为某个单词的结尾。

Trie 的核心操作流程

1. 插入单词 insert(word)

#mermaid-svg-uyBfezQTYAcBkoPh{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-uyBfezQTYAcBkoPh .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-uyBfezQTYAcBkoPh .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-uyBfezQTYAcBkoPh .error-icon{fill:#552222;}#mermaid-svg-uyBfezQTYAcBkoPh .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-uyBfezQTYAcBkoPh .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-uyBfezQTYAcBkoPh .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-uyBfezQTYAcBkoPh .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-uyBfezQTYAcBkoPh .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-uyBfezQTYAcBkoPh .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-uyBfezQTYAcBkoPh .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-uyBfezQTYAcBkoPh .marker{fill:#333333;stroke:#333333;}#mermaid-svg-uyBfezQTYAcBkoPh .marker.cross{stroke:#333333;}#mermaid-svg-uyBfezQTYAcBkoPh svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-uyBfezQTYAcBkoPh p{margin:0;}#mermaid-svg-uyBfezQTYAcBkoPh .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-uyBfezQTYAcBkoPh .cluster-label text{fill:#333;}#mermaid-svg-uyBfezQTYAcBkoPh .cluster-label span{color:#333;}#mermaid-svg-uyBfezQTYAcBkoPh .cluster-label span p{background-color:transparent;}#mermaid-svg-uyBfezQTYAcBkoPh .label text,#mermaid-svg-uyBfezQTYAcBkoPh span{fill:#333;color:#333;}#mermaid-svg-uyBfezQTYAcBkoPh .node rect,#mermaid-svg-uyBfezQTYAcBkoPh .node circle,#mermaid-svg-uyBfezQTYAcBkoPh .node ellipse,#mermaid-svg-uyBfezQTYAcBkoPh .node polygon,#mermaid-svg-uyBfezQTYAcBkoPh .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-uyBfezQTYAcBkoPh .rough-node .label text,#mermaid-svg-uyBfezQTYAcBkoPh .node .label text,#mermaid-svg-uyBfezQTYAcBkoPh .image-shape .label,#mermaid-svg-uyBfezQTYAcBkoPh .icon-shape .label{text-anchor:middle;}#mermaid-svg-uyBfezQTYAcBkoPh .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-uyBfezQTYAcBkoPh .rough-node .label,#mermaid-svg-uyBfezQTYAcBkoPh .node .label,#mermaid-svg-uyBfezQTYAcBkoPh .image-shape .label,#mermaid-svg-uyBfezQTYAcBkoPh .icon-shape .label{text-align:center;}#mermaid-svg-uyBfezQTYAcBkoPh .node.clickable{cursor:pointer;}#mermaid-svg-uyBfezQTYAcBkoPh .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-uyBfezQTYAcBkoPh .arrowheadPath{fill:#333333;}#mermaid-svg-uyBfezQTYAcBkoPh .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-uyBfezQTYAcBkoPh .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-uyBfezQTYAcBkoPh .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-uyBfezQTYAcBkoPh .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-uyBfezQTYAcBkoPh .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-uyBfezQTYAcBkoPh .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-uyBfezQTYAcBkoPh .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-uyBfezQTYAcBkoPh .cluster text{fill:#333;}#mermaid-svg-uyBfezQTYAcBkoPh .cluster span{color:#333;}#mermaid-svg-uyBfezQTYAcBkoPh div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-uyBfezQTYAcBkoPh .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-uyBfezQTYAcBkoPh rect.text{fill:none;stroke-width:0;}#mermaid-svg-uyBfezQTYAcBkoPh .icon-shape,#mermaid-svg-uyBfezQTYAcBkoPh .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-uyBfezQTYAcBkoPh .icon-shape p,#mermaid-svg-uyBfezQTYAcBkoPh .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-uyBfezQTYAcBkoPh .icon-shape rect,#mermaid-svg-uyBfezQTYAcBkoPh .image-shape rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-uyBfezQTYAcBkoPh .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-uyBfezQTYAcBkoPh .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-uyBfezQTYAcBkoPh :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

否

是

否

是

开始

取根节点

当前字符是否存在?

创建新节点

进入下一个节点

是否到达末尾?

标记 isEnd=true

结束

2. 查找单词 search(word)

逐字符遍历节点：

• 若某个字符路径不存在，返回 false
• 若遍历完成且最终节点 isEnd == true，返回 true

3. 前缀匹配 startsWith(prefix)

与 search 类似，但不关心 isEnd，只需所有前缀节点存在即可返回 true

四、复杂度分析

由于 Trie 节点彼此共享公共前缀，它在存储大量相似单词时效率极高。

五、Java 实现代码

下面给出基于数组结构的 Java 实现，结构清晰，性能稳定：

class TrieNode {
TrieNode[] children;
boolean isEnd;

public TrieNode() {
children = new TrieNode[26];
isEnd = false;
}
}

public class Trie {
private TrieNode root;

public Trie() {
root = new TrieNode();
}

// 插入单词
public void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int index = c – 'a';
if (node.children[index] == null) {
node.children[index] = new TrieNode();
}
node = node.children[index];
}
node.isEnd = true;
}

// 搜索完整单词
public boolean search(String word) {
TrieNode node = find(word);
return node != null && node.isEnd;
}

// 判断是否存在以指定前缀开始的单词
public boolean startsWith(String prefix) {
TrieNode node = find(prefix);
return node != null;
}

// 辅助函数：根据字符串查找节点
private TrieNode find(String prefix) {
TrieNode node = root;
for (char c : prefix.toCharArray()) {
int index = c – 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}

六、运行示意图（时序图）

TrieNode

Trie

User

TrieNode

Trie

User

#mermaid-svg-k0t6pt9GJHDx7xea{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-k0t6pt9GJHDx7xea .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-k0t6pt9GJHDx7xea .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-k0t6pt9GJHDx7xea .error-icon{fill:#552222;}#mermaid-svg-k0t6pt9GJHDx7xea .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-k0t6pt9GJHDx7xea .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-k0t6pt9GJHDx7xea .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-k0t6pt9GJHDx7xea .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-k0t6pt9GJHDx7xea .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-k0t6pt9GJHDx7xea .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-k0t6pt9GJHDx7xea .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-k0t6pt9GJHDx7xea .marker{fill:#333333;stroke:#333333;}#mermaid-svg-k0t6pt9GJHDx7xea .marker.cross{stroke:#333333;}#mermaid-svg-k0t6pt9GJHDx7xea svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-k0t6pt9GJHDx7xea p{margin:0;}#mermaid-svg-k0t6pt9GJHDx7xea .actor{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-k0t6pt9GJHDx7xea text.actor>tspan{fill:black;stroke:none;}#mermaid-svg-k0t6pt9GJHDx7xea .actor-line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-k0t6pt9GJHDx7xea .innerArc{stroke-width:1.5;stroke-dasharray:none;}#mermaid-svg-k0t6pt9GJHDx7xea .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333;}#mermaid-svg-k0t6pt9GJHDx7xea .messageLine1{stroke-width:1.5;stroke-dasharray:2,2;stroke:#333;}#mermaid-svg-k0t6pt9GJHDx7xea #arrowhead path{fill:#333;stroke:#333;}#mermaid-svg-k0t6pt9GJHDx7xea .sequenceNumber{fill:white;}#mermaid-svg-k0t6pt9GJHDx7xea #sequencenumber{fill:#333;}#mermaid-svg-k0t6pt9GJHDx7xea #crosshead path{fill:#333;stroke:#333;}#mermaid-svg-k0t6pt9GJHDx7xea .messageText{fill:#333;stroke:none;}#mermaid-svg-k0t6pt9GJHDx7xea .labelBox{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-k0t6pt9GJHDx7xea .labelText,#mermaid-svg-k0t6pt9GJHDx7xea .labelText>tspan{fill:black;stroke:none;}#mermaid-svg-k0t6pt9GJHDx7xea .loopText,#mermaid-svg-k0t6pt9GJHDx7xea .loopText>tspan{fill:black;stroke:none;}#mermaid-svg-k0t6pt9GJHDx7xea .loopLine{stroke-width:2px;stroke-dasharray:2,2;stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-k0t6pt9GJHDx7xea .note{stroke:#aaaa33;fill:#fff5ad;}#mermaid-svg-k0t6pt9GJHDx7xea .noteText,#mermaid-svg-k0t6pt9GJHDx7xea .noteText>tspan{fill:black;stroke:none;}#mermaid-svg-k0t6pt9GJHDx7xea .activation0{fill:#f4f4f4;stroke:#666;}#mermaid-svg-k0t6pt9GJHDx7xea .activation1{fill:#f4f4f4;stroke:#666;}#mermaid-svg-k0t6pt9GJHDx7xea .activation2{fill:#f4f4f4;stroke:#666;}#mermaid-svg-k0t6pt9GJHDx7xea .actorPopupMenu{position:absolute;}#mermaid-svg-k0t6pt9GJHDx7xea .actorPopupMenuPanel{position:absolute;fill:#ECECFF;box-shadow:0px 8px 16px 0px rgba(0,0,0,0.2);filter:drop-shadow(3px 5px 2px rgb(0 0 0 / 0.4));}#mermaid-svg-k0t6pt9GJHDx7xea .actor-man line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-k0t6pt9GJHDx7xea .actor-man circle,#mermaid-svg-k0t6pt9GJHDx7xea line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;stroke-width:2px;}#mermaid-svg-k0t6pt9GJHDx7xea :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

insert("apple")

为每个字符创建节点 a ->> p ->> p ->> l ->> e

返回最后节点

插入完成

search("app")

查找 a ->> p ->> p

查找结束

返回 false（未标为结束）

startsWith("app")

查找前缀路径

前缀存在

返回 true

七、优化与扩展

• 可扩展字符集： 如果需要支持 Unicode 或大小写混合，可以将 children 改为 Map<Character, TrieNode>。
• 删除操作： 可通过递归方式实现，当某节点无其他分支且非单词结尾时可清理。
• 前缀搜索应用： 如自动补全、词频统计等。

Trie 是一种非常有价值的数据结构，在 搜索引擎自动补全、拼写校验、字符串匹配 等场景中广泛应用。 其核心优势在于 以空间换时间，在字符层级组织信息，快速定位前缀路径。