实现前缀树TrieLeetCode 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 iendOfWord布尔值标记该节点是否为一个完整单词的结尾。class TrieNode: def __init__(self): self.children [None] * 26 self.endOfWord FalseInsert(word)插入单词从根节点root开始依次处理单词中的每个字符将字符转换为下标c - a若对应子节点不存在则创建新节点移动到该子节点处理完所有字符后将当前节点的endOfWord置为true。Search(word)精确查找单词从根节点root开始依次处理每个字符移动到对应子节点若某字符对应的子节点缺失直接返回false遍历结束后仅当endOfWord为true时返回true——这保证了「只作为前缀存在但并非完整单词」的字符串不会被误判为单词。StartsWith(prefix)检查前缀从根节点root开始依次遍历前缀中的字符并下移若所有字符都能沿路径找到返回true无需检查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 Truepublic 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 arrayOfNullsTrieNode(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: [OptionBoxTrieNode; 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 - ba) 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 - ba) 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 - ba) 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 Truepublic class TrieNode { HashMapCharacter, 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_mapchar, 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 Dictionarychar, TrieNode children new Dictionarychar, 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 mutableMapOfChar, 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: HashMapchar, 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)应返回trueapp是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数组实现节点属性命名为childrenend并保留 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 回溯体会「哈希表存储 递归搜索」的组合威力单词搜索 IILeetCode 212见 python/0212-word-search-ii.py将全部单词插入 Trie 后在网格上做 DFS 剪枝并引入refs引用计数来标记节点是否仍被剩余单词使用命中单词后从根路径递减计数、避免无效回溯是 Trie 回溯 剪枝的经典综合题对应文章 articles/search-for-word-ii.md自动补全系统LeetCode 642见 articles/design-search-autocomplete-system.mdTrie 是自动补全功能的核心底层前缀与后缀检索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.mdTrie 可作为字典查找的加速结构配合 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考