用 javascript 分类刷 leetcode22. 字典树 (图文视频讲解)
目录
Trie 树,即字典树,又称前缀树,是一种树形结构,典型应用是用于统计和排序大量的字符串(但不限于字符串),所以经常被搜索引擎用于文本词频统计。它的优先是,最大限度的减少无谓的字符串比较,提高查找效率。
Trie 的核心思想是空间换时间,利用字符串的公共前缀来降低查询时间的开销,以达到提高效率的目的
基本性质
根节点不包含字符,除跟节点外每个节点都只包含一个字符
从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串
每个节点的所有子节点包含的字符都不相同
![](https://static001.geekbang.org/infoq/6f/6f250a49dbe179a49af1d3b0958d40f4.png)
实际应用,例如搜索
![](https://static001.geekbang.org/infoq/58/580a817b526c40e029dbce31d380b9d6.png)
720. 词典中最长的单词 (easy)
给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词,该单词是由 words 词典中其他单词逐步添加一个字母组成。
若其中有多个可行的答案,则返回答案中字典序最小的单词。若无答案,则返回空字符串。
示例 1:
输入:words = ["w","wo","wor","worl", "world"]输出:"world"解释: 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。示例 2:
输入:words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]输出:"apple"解释:"apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply"
提示:
1 <= words.length <= 10001 <= words[i].length <= 30 所有输入的字符串 words[i] 都只包含小写字母。
方法 1:sort+hash
思路:排序数组,然后遍历字符串数组,判断数组中的每个字符串的子串是否都在数组中
复杂度:时间复杂度
O(mn)
,m 是字符串数组的长度,n 是字符串最大长度。空间复杂度O(m)
js:
方法 2:字典树
![](https://static001.geekbang.org/infoq/69/691a94d2eac5ef24c26593bf5020f10b.png)
思路:将所有字符串插入 trie 中,递归寻找那个长度最大的单词
复杂度:时间复杂度
O(mn)
,m 是字符串数组的长度,n 是字符串最大长度。空间复杂度O(
∑w)
。递归深度不会超过最长单词长度,字段书的空间复杂度是所有字符串的长度和。
js:
212. 单词搜索 II (hard)
给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词,该单词是由 words 词典中其他单词逐步添加一个字母组成。
若其中有多个可行的答案,则返回答案中字典序最小的单词。若无答案,则返回空字符串。
示例 1:
输入:words = ["w","wo","wor","worl", "world"]输出:"world"解释: 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。示例 2:
输入:words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]输出:"apple"解释:"apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply"
提示:
1 <= words.length <= 10001 <= words[i].length <= 30 所有输入的字符串 words[i] 都只包含小写字母。
![](https://static001.geekbang.org/infoq/87/8736bdf41742671e39fa801d97ab1697.jpeg?x-oss-process=image%2Fresize%2Cp_80%2Fauto-orient%2C1)
思路:将 words 数组中的所有字符串加入 Trie 中,然后遍历网格,判断网格路径形成的字符串在不在 Trie 中,然后上下左右四个方向不断回溯尝试。
复杂度分析:时间复杂度
O(MN⋅3^L)
,空间复杂度是O(max(MN, KL))
,visited 空间是O(MN),
字典树O(KL)
,L 是最长字符串的长度,K 是 words 数组的长度。dfs 递归栈的最大深度是O(min(L,MN))
,
方法 1.Trie
Js:
208. 实现 Trie (前缀树)(medium)
Trie(发音类似 "try")或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类:
Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中,返回 true(即,在检索之前已经插入);否则,返回 false 。boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ,返回 true ;否则,返回 false 。
示例:
输入["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"); // 返回 Truetrie.search("app"); // 返回 Falsetrie.startsWith("app"); // 返回 Truetrie.insert("app");trie.search("app"); // 返回 True
提示:
1 <= word.length, prefix.length <= 2000word 和 prefix 仅由小写英文字母组成 insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次
![](https://static001.geekbang.org/infoq/6f/6f250a49dbe179a49af1d3b0958d40f4.png)
思路:本题这字符集长度是 26,即 26 个小写英文字母,isEnd 表示该节点是否是字符串的结尾。
插入字符串:从字段树的根节点开始,如果子节点存在,继续处理下一个字符,如果子节点不存在,则创建一个子节点到 children 的相应位置,沿着指针继续向后移动,处理下一个字符,以插入‘cad’为例
查找前缀:从根节点开始,子节点存在,则沿着指针继续搜索下一个子节点,直到最后一个,如果搜索到了前缀所有字符,说明字典树包含该前缀。子节点不存在就说明字典树中不包含该前缀,返回 false。
查找字符串:和查找前缀一样,只不过最后返回的节点的 isEnd 是 true,也就是说字符串正好是字典树的一个分支
复杂度分析:时间复杂度,初始化为
O(1)
,其余操作为O(S)
,s 为字符串的长度。空间复杂度为O(T)
,T 为字符集的大小,本题是 26
js:
视频讲解:传送门
评论