实现前缀树（Trie）：LeetCode 208 题数组与哈希表双解法全解析

实现前缀树（Trie）：LeetCode 208 题数组与哈希表双解法全解析

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

前缀树（Prefix Tree / Trie）是一种以共享前缀为核心、专为快速字符串操作设计的多叉树结构，是字典查询、自动补全、前缀匹配等场景的基础数据结构。本篇以 LeetCode 208「实现 Trie（前缀树）」为背景，完整讲解基于 26 元素数组与基于哈希表两种实现方案的节点设计、insert/search/startsWith三大操作流程，并结合本仓库 python/0208-implement-trie-prefix-tree.py、cpp/0208-implement-trie-prefix-tree.cpp 等真实题解与 hints/implement-prefix-tree.md 官方提示，逐行印证实现细节。读完本文，你将能够独立写出多语言版本的前缀树，并掌握search与startsWith的根本区别及常见踩坑点，为后续解决单词搜索、自动补全、前缀后缀检索等进阶问题打下基础。

前置知识

在动手实现前缀树之前，建议先熟悉以下四项基础能力，它们是理解本数据结构的前提：

• 树形数据结构（Tree Data Structures）：理解父子节点关系与树的遍历方式，前缀树本质是一棵每个节点至多代表一个字符的多叉树。
• 子节点的哈希表 / 数组存储（Hash Maps / Arrays for Children）：前缀树两种主流实现分别用定长数组与哈希表存放子节点引用，需要熟悉两者的索引/键值操作。
• 字符串处理（String Processing）：逐字符迭代字符串，以及字符到数组下标的 ASCII 换算（如c - 'a'）。
• 面向对象设计（Object-Oriented Design）：通过类封装节点状态（子节点 + 结束标记），对外暴露insert、search、startsWith三个方法。

1. 前缀树（数组实现）

核心直觉

前缀树是一种专为快速字符串操作设计的树状数据结构：每个节点代表一个字符，从根到某个节点的路径就对应一个字符串前缀，因此公共前缀被所有单词共享，能够显著节省存储空间。

数组实现的关键设计：

• 每个节点固定拥有26 个子节点（对应小写字母a–z），用字符位置直接作为下标访问；
• 一个布尔标志位endOfWord标记「是否有完整单词在此节点结束」；
• 根节点不存储任何字符，仅作为所有操作的入口。

为什么前缀树有用：

• 单词查找与前缀查找的时间复杂度为O(单词长度)，与字典中已存储的单词总量无关；
• 天然适配字典查询（dictionary lookups）、自动补全（autocomplete）、前缀检查（prefix checks）等场景。

数据结构定义

数组实现的节点包含两部分：

• children[26]：长度为 26 的子节点指针数组，children[i]对应字符'a' + i；
• endOfWord：布尔值，标记该节点是否为一个完整单词的结尾。

class TrieNode: def __init__(self): self.children = [None] * 26 self.endOfWord = False

Insert(word)：插入单词

1. 从根节点root开始；
2. 依次处理单词中的每个字符：
   • 将字符转换为下标（c - 'a'）；
   • 若对应子节点不存在，则创建新节点；
   • 移动到该子节点；
3. 处理完所有字符后，将当前节点的endOfWord置为true。

Search(word)：精确查找单词

1. 从根节点root开始；
2. 依次处理每个字符，移动到对应子节点；
3. 若某字符对应的子节点缺失，直接返回false；
4. 遍历结束后，仅当endOfWord为true时返回true——这保证了「只作为前缀存在但并非完整单词」的字符串不会被误判为单词。

StartsWith(prefix)：检查前缀

1. 从根节点root开始；
2. 依次遍历前缀中的字符并下移；
3. 若所有字符都能沿路径找到，返回true；
4. 无需检查endOfWord——前缀只要路径存在即可。

多语言完整实现

以下为数组方案在 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言中的完整实现，代码逻辑完全一致，可对照学习字符索引换算在不同语言中的写法差异：

class TrieNode: def __init__(self): self.children = [None] * 26 self.endOfWord = False class PrefixTree: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: cur = self.root for c in word: i = ord(c) - ord("a") if cur.children[i] == None: cur.children[i] = TrieNode() cur = cur.children[i] cur.endOfWord = True def search(self, word: str) -> bool: cur = self.root for c in word: i = ord(c) - ord("a") if cur.children[i] == None: return False cur = cur.children[i] return cur.endOfWord def startsWith(self, prefix: str) -> bool: cur = self.root for c in prefix: i = ord(c) - ord("a") if cur.children[i] == None: return False cur = cur.children[i] return True

public class TrieNode { TrieNode[] children = new TrieNode[26]; boolean endOfWord = false; } public class PrefixTree { private TrieNode root; public PrefixTree() { root = new TrieNode(); } public void insert(String word) { TrieNode cur = root; for (char c : word.toCharArray()) { int i = c - 'a'; if (cur.children[i] == null) { cur.children[i] = new TrieNode(); } cur = cur.children[i]; } cur.endOfWord = true; } public boolean search(String word) { TrieNode cur = root; for (char c : word.toCharArray()) { int i = c - 'a'; if (cur.children[i] == null) { return false; } cur = cur.children[i]; } return cur.endOfWord; } public boolean startsWith(String prefix) { TrieNode cur = root; for (char c : prefix.toCharArray()) { int i = c - 'a'; if (cur.children[i] == null) { return false; } cur = cur.children[i]; } return true; } }

class TrieNode { public: TrieNode* children[26]; bool endOfWord; TrieNode() { for (int i = 0; i < 26; i++) { children[i] = nullptr; } endOfWord = false; } }; class PrefixTree { TrieNode* root; public: PrefixTree() { root = new TrieNode(); } void insert(string word) { TrieNode* cur = root; for (char c : word) { int i = c - 'a'; if (cur->children[i] == nullptr) { cur->children[i] = new TrieNode(); } cur = cur->children[i]; } cur->endOfWord = true; } bool search(string word) { TrieNode* cur = root; for (char c : word) { int i = c - 'a'; if (cur->children[i] == nullptr) { return false; } cur = cur->children[i]; } return cur->endOfWord; } bool startsWith(string prefix) { TrieNode* cur = root; for (char c : prefix) { int i = c - 'a'; if (cur->children[i] == nullptr) { return false; } cur = cur->children[i]; } return true; } };

class TrieNode { constructor() { this.children = new Array(26).fill(null); this.endOfWord = false; } } class PrefixTree { constructor() { this.root = new TrieNode(); } /** * @param {string} word * @return {void} */ insert(word) { let cur = this.root; for (let c of word) { let i = c.charCodeAt(0) - 97; if (cur.children[i] === null) { cur.children[i] = new TrieNode(); } cur = cur.children[i]; } cur.endOfWord = true; } /** * @param {string} word * @return {boolean} */ search(word) { let cur = this.root; for (let c of word) { let i = c.charCodeAt(0) - 97; if (cur.children[i] === null) { return false; } cur = cur.children[i]; } return cur.endOfWord; } /** * @param {string} prefix * @return {boolean} */ startsWith(prefix) { let cur = this.root; for (let c of prefix) { let i = c.charCodeAt(0) - 97; if (cur.children[i] === null) { return false; } cur = cur.children[i]; } return true; } }

public class TrieNode { public TrieNode[] children = new TrieNode[26]; public bool endOfWord = false; } public class PrefixTree { private TrieNode root; public PrefixTree() { root = new TrieNode(); } public void Insert(string word) { TrieNode cur = root; foreach (char c in word) { int i = c - 'a'; if (cur.children[i] == null) { cur.children[i] = new TrieNode(); } cur = cur.children[i]; } cur.endOfWord = true; } public bool Search(string word) { TrieNode cur = root; foreach (char c in word) { int i = c - 'a'; if (cur.children[i] == null) { return false; } cur = cur.children[i]; } return cur.endOfWord; } public bool StartsWith(string prefix) { TrieNode cur = root; foreach (char c in prefix) { int i = c - 'a'; if (cur.children[i] == null) { return false; } cur = cur.children[i]; } return true; } }

type TrieNode struct { children [26]*TrieNode endOfWord bool } type PrefixTree struct { root *TrieNode } func Constructor() PrefixTree { return PrefixTree{root: &TrieNode{}} } func (this *PrefixTree) Insert(word string) { cur := this.root for _, c := range word { i := c - 'a' if cur.children[i] == nil { cur.children[i] = &TrieNode{} } cur = cur.children[i] } cur.endOfWord = true } func (this *PrefixTree) Search(word string) bool { cur := this.root for _, c := range word { i := c - 'a' if cur.children[i] == nil { return false } cur = cur.children[i] } return cur.endOfWord } func (this *PrefixTree) StartsWith(prefix string) bool { cur := this.root for _, c := range prefix { i := c - 'a' if cur.children[i] == nil { return false } cur = cur.children[i] } return true }

class TrieNode { val children = arrayOfNulls<TrieNode>(26) var endOfWord = false } class PrefixTree { private val root = TrieNode() fun insert(word: String) { var cur = root for (c in word) { val i = c - 'a' if (cur.children[i] == null) { cur.children[i] = TrieNode() } cur = cur.children[i]!! } cur.endOfWord = true } fun search(word: String): Boolean { var cur = root for (c in word) { val i = c - 'a' if (cur.children[i] == null) { return false } cur = cur.children[i]!! } return cur.endOfWord } fun startsWith(prefix: String): Boolean { var cur = root for (c in prefix) { val i = c - 'a' if (cur.children[i] == null) { return false } cur = cur.children[i]!! } return true } }

class TrieNode { var children: [TrieNode?] var endOfWord: Bool init() { self.children = Array(repeating: nil, count: 26) self.endOfWord = false } } class PrefixTree { private let root: TrieNode init() { self.root = TrieNode() } func insert(_ word: String) { var cur = root for c in word { let i = Int(c.asciiValue! - Character("a").asciiValue!) if cur.children[i] == nil { cur.children[i] = TrieNode() } cur = cur.children[i]! } cur.endOfWord = true } func search(_ word: String) -> Bool { var cur = root for c in word { let i = Int(c.asciiValue! - Character("a").asciiValue!) if cur.children[i] == nil { return false } cur = cur.children[i]! } return cur.endOfWord } func startsWith(_ prefix: String) -> Bool { var cur = root for c in prefix { let i = Int(c.asciiValue! - Character("a").asciiValue!) if cur.children[i] == nil { return false } cur = cur.children[i]! } return true } }

struct TrieNode { children: [Option<Box<TrieNode>>; 26], end_of_word: bool, } impl TrieNode { fn new() -> Self { Self { children: Default::default(), end_of_word: false, } } } struct PrefixTree { root: TrieNode, } impl PrefixTree { fn new() -> Self { Self { root: TrieNode::new() } } fn insert(&mut self, word: String) { let mut cur = &mut self.root; for c in word.bytes() { let i = (c - b'a') as usize; cur = cur.children[i].get_or_insert_with(|| Box::new(TrieNode::new())); } cur.end_of_word = true; } fn search(&self, word: String) -> bool { let mut cur = &self.root; for c in word.bytes() { let i = (c - b'a') as usize; match &cur.children[i] { Some(node) => cur = node, None => return false, } } cur.end_of_word } fn starts_with(&self, prefix: String) -> bool { let mut cur = &self.root; for c in prefix.bytes() { let i = (c - b'a') as usize; match &cur.children[i] { Some(node) => cur = node, None => return false, } } true } }

复杂度分析（数组实现）

• 时间复杂度：每次调用均为O(n)；
• 空间复杂度：O(t)。

其中n为传入字符串的长度，t为前缀树中创建的TrieNode节点总数（注意：insert最坏会新建 O(n) 个节点，而search/startsWith只沿路径遍历、不额外分配空间）。

2. 前缀树（哈希表实现）

当字符集不固定（例如包含大写字母、数字甚至 Unicode 字符），或者不希望为每个节点都预分配 26 个槽位时，可以改用哈希表存储子节点：键为字符本身，值为子节点引用。这样仅存储实际存在的字符边，避免了数组方案的固定内存开销，代码也更为简洁——不再需要字符到下标的换算，直接用字符作为键访问即可。

class TrieNode: def __init__(self): self.children = {} self.endOfWord = False class PrefixTree: def __init__(self): self.root = TrieNode() def insert(self, word: str) -> None: cur = self.root for c in word: if c not in cur.children: cur.children[c] = TrieNode() cur = cur.children[c] cur.endOfWord = True def search(self, word: str) -> bool: cur = self.root for c in word: if c not in cur.children: return False cur = cur.children[c] return cur.endOfWord def startsWith(self, prefix: str) -> bool: cur = self.root for c in prefix: if c not in cur.children: return False cur = cur.children[c] return True

public class TrieNode { HashMap<Character, TrieNode> children = new HashMap<>(); boolean endOfWord = false; } public class PrefixTree { private TrieNode root; public PrefixTree() { root = new TrieNode(); } public void insert(String word) { TrieNode cur = root; for (char c : word.toCharArray()) { cur.children.putIfAbsent(c, new TrieNode()); cur = cur.children.get(c); } cur.endOfWord = true; } public boolean search(String word) { TrieNode cur = root; for (char c : word.toCharArray()) { if (!cur.children.containsKey(c)) { return false; } cur = cur.children.get(c); } return cur.endOfWord; } public boolean startsWith(String prefix) { TrieNode cur = root; for (char c : prefix.toCharArray()) { if (!cur.children.containsKey(c)) { return false; } cur = cur.children.get(c); } return true; } }

class TrieNode { public: unordered_map<char, TrieNode*> children; bool endOfWord = false; }; class PrefixTree { TrieNode* root; public: PrefixTree() { root = new TrieNode(); } void insert(string word) { TrieNode* cur = root; for (char c : word) { if (cur->children.find(c) == cur->children.end()) { cur->children[c] = new TrieNode(); } cur = cur->children[c]; } cur->endOfWord = true; } bool search(string word) { TrieNode* cur = root; for (char c : word) { if (cur->children.find(c) == cur->children.end()) { return false; } cur = cur->children[c]; } return cur->endOfWord; } bool startsWith(string prefix) { TrieNode* cur = root; for (char c : prefix) { if (cur->children.find(c) == cur->children.end()) { return false; } cur = cur->children[c]; } return true; } };

class TrieNode { constructor() { this.children = new Map(); this.endOfWord = false; } } class PrefixTree { constructor() { this.root = new TrieNode(); } /** * @param {string} word * @return {void} */ insert(word) { let cur = this.root; for (let c of word) { if (!cur.children.has(c)) { cur.children.set(c, new TrieNode()); } cur = cur.children.get(c); } cur.endOfWord = true; } /** * @param {string} word * @return {boolean} */ search(word) { let cur = this.root; for (let c of word) { if (!cur.children.has(c)) { return false; } cur = cur.children.get(c); } return cur.endOfWord; } /** * @param {string} prefix * @return {boolean} */ startsWith(prefix) { let cur = this.root; for (let c of prefix) { if (!cur.children.has(c)) { return false; } cur = cur.children.get(c); } return true; } }

public class TrieNode { public Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>(); public bool endOfWord = false; } public class PrefixTree { private TrieNode root; public PrefixTree() { root = new TrieNode(); } public void Insert(string word) { TrieNode cur = root; foreach (char c in word) { if (!cur.children.ContainsKey(c)) { cur.children[c] = new TrieNode(); } cur = cur.children[c]; } cur.endOfWord = true; } public bool Search(string word) { TrieNode cur = root; foreach (char c in word) { if (!cur.children.ContainsKey(c)) { return false; } cur = cur.children[c]; } return cur.endOfWord; } public bool StartsWith(string prefix) { TrieNode cur = root; foreach (char c in prefix) { if (!cur.children.ContainsKey(c)) { return false; } cur = cur.children[c]; } return true; } }

type TrieNode struct { children map[rune]*TrieNode endOfWord bool } type PrefixTree struct { root *TrieNode } func Constructor() PrefixTree { return PrefixTree{root: &TrieNode{children: make(map[rune]*TrieNode)}} } func (this *PrefixTree) Insert(word string) { cur := this.root for _, c := range word { if cur.children[c] == nil { cur.children[c] = &TrieNode{children: make(map[rune]*TrieNode)} } cur = cur.children[c] } cur.endOfWord = true } func (this *PrefixTree) Search(word string) bool { cur := this.root for _, c := range word { if cur.children[c] == nil { return false } cur = cur.children[c] } return cur.endOfWord } func (this *PrefixTree) StartsWith(prefix string) bool { cur := this.root for _, c := range prefix { if cur.children[c] == nil { return false } cur = cur.children[c] } return true }

class TrieNode { val children = mutableMapOf<Char, TrieNode>() var endOfWord = false } class PrefixTree { private val root = TrieNode() fun insert(word: String) { var cur = root for (c in word) { cur.children.putIfAbsent(c, TrieNode()) cur = cur.children[c]!! } cur.endOfWord = true } fun search(word: String): Boolean { var cur = root for (c in word) { if (c !in cur.children) { return false } cur = cur.children[c]!! } return cur.endOfWord } fun startsWith(prefix: String): Boolean { var cur = root for (c in prefix) { if (c !in cur.children) { return false } cur = cur.children[c]!! } return true } }

class TrieNode { var children: [Character: TrieNode] var endOfWord: Bool init() { self.children = [:] self.endOfWord = false } } class PrefixTree { private let root: TrieNode init() { self.root = TrieNode() } func insert(_ word: String) { var cur = root for c in word { if cur.children[c] == nil { cur.children[c] = TrieNode() } cur = cur.children[c]! } cur.endOfWord = true } func search(_ word: String) -> Bool { var cur = root for c in word { if cur.children[c] == nil { return false } cur = cur.children[c]! } return cur.endOfWord } func startsWith(_ prefix: String) -> Bool { var cur = root for c in prefix { if cur.children[c] == nil { return false } cur = cur.children[c]! } return true } }

use std::collections::HashMap; struct TrieNode { children: HashMap<char, TrieNode>, end_of_word: bool, } impl TrieNode { fn new() -> Self { Self { children: HashMap::new(), end_of_word: false, } } } struct PrefixTree { root: TrieNode, } impl PrefixTree { fn new() -> Self { Self { root: TrieNode::new() } } fn insert(&mut self, word: String) { let mut cur = &mut self.root; for c in word.chars() { cur = cur.children.entry(c).or_insert_with(TrieNode::new); } cur.end_of_word = true; } fn search(&self, word: String) -> bool { let mut cur = &self.root; for c in word.chars() { match cur.children.get(&c) { Some(node) => cur = node, None => return false, } } cur.end_of_word } fn starts_with(&self, prefix: String) -> bool { let mut cur = &self.root; for c in prefix.chars() { match cur.children.get(&c) { Some(node) => cur = node, None => return false, } } true } }

复杂度分析（哈希表实现）

• 时间复杂度：每次调用仍为O(n)；
• 空间复杂度：O(t)，其中n为字符串长度，t为创建的节点总数。

与数组方案相比，哈希表方案单次查找的常数因子略高（哈希计算与扩容），但在字符集稀疏或未知时内存利用率更高。若题目明确限定为小写英文字母（如 LeetCode 208），数组方案通常更快；若字符集开放或包含通配符扩展，哈希表方案更灵活。

常见陷阱与避坑指南

陷阱一：混淆 search 与 startsWith

最频繁的错误是：只要search()沿路径完整走完就返回true，却忘了检查endOfWord标志位。search()必须确认最终节点标记了某个完整单词的结束，而startsWith()只要求前缀路径存在即可。

举例：假设已插入"apple"，则search("app")应返回false（没有任何单词在app处结束），而startsWith("app")应返回true（app是apple的前缀）。请务必在search末尾返回cur.endOfWord，在startsWith末尾直接返回true。

陷阱二：字符索引计算错误

数组方案要求把字符换算成下标：c - 'a'。常见错误包括：

• 直接使用 ASCII 值（如ord(c)/charCodeAt(0)）而不减去'a'，导致下标越界；
• 错误假设输入包含大写字母——若字符集是大写，应使用c - 'A'；
• 必须保证输入约束与索引方案一致：例如题目保证只含小写英文字母时，26个槽位与c - 'a'才能匹配。

陷阱三：忘记初始化子节点

在insert()向下遍历时，若子节点不存在却没有先创建，后续对null的访问会引发空指针异常。必须先判断再创建：

if cur.children[i] == None: cur.children[i] = TrieNode() cur = cur.children[i] # 必须先创建，再下移

哈希表方案同理：在访问键之前必须先put/set该字符键，否则会发生 KeyError 或取到undefined。

仓库实战印证：真实题解与进阶延伸

本题（LeetCode 208）的真实题解对照

本仓库针对本题提供了多语言可直接运行的实现，与上文讲解一一对应：

• python/0208-implement-trie-prefix-tree.py：数组实现，节点属性命名为children+end，并保留 LeetCode 官方注释「Initialize your data structure here.」等接口说明；
• cpp/0208-implement-trie-prefix-tree.cpp：数组实现，构造函数显式将 26 个指针初始化为NULL，并注释了「Time: O(n) insert, O(n) search, O(n) startsWith / Space: O(n) insert, O(1) search, O(1) startsWith」的复杂度说明；
• go/0208-implement-trie-prefix-tree.go：数组实现，Constructor()返回Trie结构体，符合 Go 题解的惯用写法；
• javascript/0208-implement-trie-prefix-tree.js：基于对象（{}）的哈希表实现，用children[char]直接以字符为键，并在每个方法上标注了Time O(N) / Space O(N)等复杂度。

另外 hints/implement-prefix-tree.md 提供了官方提示：推荐每个函数调用达到O(n) 时间、O(t) 空间；插入时若当前节点已含word[i]则直接下移，否则新建节点并在末尾置结束标志；搜索时缺字符或结束标志未置位则返回false——与本文算法流程完全一致。

前缀树的进阶应用（仓库内相关题解）

掌握基础实现后，可以继续阅读仓库内以下基于 Trie 的进阶题目，观察同一数据结构在复杂场景下的演化：

• 带通配符的单词搜索（LeetCode 211）：见 python/0211-design-add-and-search-words-data-structure.py，在search中遇到'.'通配符时对当前节点的所有子节点做 DFS 回溯，体会「哈希表存储 + 递归搜索」的组合威力；
• 单词搜索 II（LeetCode 212）：见 python/0212-word-search-ii.py，将全部单词插入 Trie 后在网格上做 DFS 剪枝，并引入refs引用计数来标记节点是否仍被剩余单词使用，命中单词后从根路径递减计数、避免无效回溯，是 Trie + 回溯 + 剪枝的经典综合题，对应文章 articles/search-for-word-ii.md；
• 自动补全系统（LeetCode 642）：见 articles/design-search-autocomplete-system.md，Trie 是自动补全功能的核心底层；
• 前缀与后缀检索（LeetCode 745）：见 articles/prefix-and-suffix-search.md 与 python/0745-prefix-and-suffix-search.py，利用 Trie 存储带分隔符的「后缀 + 前缀」组合键；
• 单词拆分（LeetCode 139/140）：见 articles/word-break.md、articles/word-break-ii.md，Trie 可作为字典查找的加速结构配合 DP 使用。

这些题目说明：前缀树的本质价值在于把「字符串集合」压缩成一棵可沿前缀快速导航的树，任何需要频繁做「某串是否在集合中」「某前缀是否存在」判断的问题，都值得优先考虑 Trie。

小结

本文围绕前缀树的两种实现展开了完整讲解：数组方案利用固定 26 槽位 +c - 'a'下标换算，在限定小写字母时空间紧凑、访问直接；哈希表方案以字符为键动态扩展，适用于字符集开放或稀疏的场景。两者的insert、search、startsWith均为 O(单词长度) 时间，区别仅在于search必须校验endOfWord而startsWith不需要。牢记「先创建子节点再下移」「正确换算字符下标」「区分完整单词与前缀」三大要点，再结合仓库内 python/0208-implement-trie-prefix-tree.py 等真实题解逐行对照，即可牢固掌握这一高频数据结构，并顺利过渡到通配符搜索、单词搜索、自动补全等进阶题目。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode