关键词：
前言
本题为 LeetCode 前 100 高频题
我们社区陆续会将顾毅（Netflix 增长，《iOS 面试之道》作者，ACE 职业健身教练。）的 Swift 算法题题解整理为文字版以方便大家学习与阅读。
LeetCode 算法到目前我们已经更新到 207 期，我们会保持更新时间和进度（周一、周三、周五早上 9:00 发布），每期的内容不多，我们希望大家可以在上班路上阅读，长久积累会有很大提升。
不积跬步，无以至千里；不积小流，无以成江海，Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言，我们会尽力满足大家的需求。
难度水平：中等
1. 描述
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
请你实现 Trie 类：
-
Trie() 初始化前缀树对象。 -
void insert(String word) 向前缀树中插入字符串word 。 -
boolean search(String word) 如果字符串word 在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false 。 -
boolean startsWith(String prefix) 如果之前已经插入的字符串word 的前缀之一为prefix ，返回true ；否则，返回false 。
2. 示例
示例
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]
解释
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
提示：
-
1 <= word.length, prefix.length <= 2000 -
word 和prefix 仅由小写英文字母组成 -
insert、search 和startsWith 调用次数 总计 不超过3 * 10^4 次
3. 答案
class Trie
private var nodes: [Character: Trie]
/** Initialize your data structure here. */
init()
nodes = [:]
/** Inserts a word into the trie. */
func insert(_ word: String)
var trie = self
word.forEach
if let subTrie = trie.nodes[$0]
trie = subTrie
else
let subTrie = Trie()
trie.nodes[$0] = subTrie
trie = subTrie
trie.nodes["#"] = Trie()
/** Returns if the word is in the trie. */
func search(_ word: String) -> Bool
var trie = self
for char in word
guard let subTrie = trie.nodes[char] else
return false
trie = subTrie
return trie.nodes["#"] != nil;
/** Returns if there is any word in the trie that starts with the given prefix. */
func startsWith(_ prefix: String) -> Bool
var trie = self
for char in prefix
guard let subTrie = trie.nodes[char] else
return false
trie = subTrie
return true
- 主要思想：实现一个树数据结构，其中每个节点都有一个字典，存储所有具有公共前缀的后代。
- 时间复杂度：
O(m)，其中m 是目标字符串的长度 - 空间复杂度：
insert - O(m),search - O(1),startsWith - O(1)
该算法题解的仓库：LeetCode-Swift
点击前往 LeetCode 练习
关于我们
我们是由 Swift 爱好者共同维护，我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容，也整理收集优秀的学习资料。
[javascript刷题]树-实现前缀树,leetcode208(代码片段)
[JavaScript刷题]树-实现前缀树,leetcode208githubrepo地址:https://github.com/GoldenaArcher/js_leetcode，Github的目录大概会更新的更勤快一些。题目地址：208.ImplementTrie(PrefixTree)题目如下：Atrie(pronouncedas“try”)orprefixtreeisatreedatastructureus... 查看详情
[javascript刷题]树-实现前缀树,leetcode208(代码片段)
[JavaScript刷题]树-实现前缀树,leetcode208githubrepo地址:https://github.com/GoldenaArcher/js_leetcode，Github的目录大概会更新的更勤快一些。题目地址：208.ImplementTrie(PrefixTree)题目如下：Atrie(pronouncedas“try”)orprefixtreeisatreedatastructureus... 查看详情
字典树208.实现trie(前缀树)(代码片段)
208.实现Trie(前缀树)难度中等886Trie（发音类似"try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。请你实... 查看详情
力扣208——实现trie(前缀树)(代码片段)
...?构成的。保证所有输入均为非空字符串。原题url：https://leetcode-cn.com/problems/implement-trie-prefix-tree/解题前缀树的意义我们用前缀树这种数据结构，主要是用在在字符串数据集中搜索单词的场景，但针对这种场景，我们也可以使用... 查看详情
208.实现trie(前缀树)(代码片段)
实现Trie(前缀树)Trie（发音类似“try”）或者说前缀树是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。请你实现Trie类：Trie()初... 查看详情
java208.实现trie（前缀树）.java(代码片段)
java208.实现trie（前缀树）.java(代码片段)
java208.实现trie（前缀树）.java(代码片段)
java208.实现trie（前缀树）.java(代码片段)
java208.实现trie（前缀树）.java(代码片段)
java208.实现trie（前缀树）.java(代码片段)
208implementtrie(prefixtree)字典树（前缀树）
实现一个Trie(前缀树)，包含insert,search,和startsWith这三个方法。注意:你可以假设所有的输入都是小写字母a-z。详见：https://leetcode.com/problems/implement-trie-prefix-tree/description/classTrieNodepublic:TrieNode*next[26];charc;boolisWord;Tr 查看详情
[208].实现trie（前缀树）(代码片段)
...;前缀树）题目函数原型字典树 题目题目：https://leetcode-cn.com/problems/implement-trie-prefix-tree/ 函数原型classTriepublic:Trie()voidinsert(stringword)boolsearch(stringword)boolstartsWith(stringprefix); 字典树字典树，又名前缀树。最大的特点在... 查看详情
[208].实现trie（前缀树）(代码片段)
...;前缀树）题目函数原型字典树 题目题目：https://leetcode-cn.com/problems/implement-trie-prefix-tree/ 函数原型classTriepublic:Trie()voidinsert(stringword)boolsearch(stringword)boolstartsWith(stringprefix); 字典树字典树，又名前缀树。最大的特点在... 查看详情
实现前缀树(代码片段)
参考：【设计数据结构】实现Trie(前缀树)208.实现Trie树Trie树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。其核心是使用「边」来代表有无字符，使用「点」来记录是否为... 查看详情
java刷题--208trie前缀树(代码片段)
java刷题--208Trie前缀树题目代码结果题目腾讯二面–所以说知识点一定要全代码classTrieprivateTrie[]children;privatebooleanisEnd;publicTrie()children=newTrie[26];isEnd=false;publicvoidinsert(Stringword)Trienode=this;for 查看详情
208.implementtrie(prefixtree)实现前缀树
Implementatriewithinsert,search,andstartsWithmethods.Note:Youmayassumethatallinputsareconsistoflowercaselettersa-z. varTrie=function(){this.nodes={};};Trie.prototype.insert=function(word){l 查看详情
208.implementtrie(prefixtree)(代码片段)
原题链接：https://leetcode.com/problems/implement-trie-prefix-tree/description/都是前缀树相关的题目。LeetCode上面刷题时可以查看SimilarQuestions问题，这道题目也是做211.AddandSearchWord-Datastructuredesign这道题目看到的。这道题目就很简单的，我之... 查看详情