leetcode-implement-trie-prefix-tree
题目介绍
原题链接:https://leetcode.com/problems/implement-trie-prefix-tree/
208. Implement Trie (Prefix Tree)
- difficulty:Medium
Implement a trie with insert
, search
, and startsWith
methods.
Example:
1 | Trie trie = new Trie(); |
Note:
- You may assume that all inputs are consist of lowercase letters
a-z
. - All inputs are guaranteed to be non-empty strings.
思路
在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。
- 首先定义一个节点TrieNode,有两个元素,一个是children,代表孩子,总长度是字母表的个数,另一个是isEnd,表示是否是单词结尾(叶子)
- Trie树有一个根节点root
- 不同的叶子可能有公共的前缀
插入
- 键值为字符串,长度为m
- 遍历键值中的每个字符,当此位置的孩子为空时插入节点,不为空时,当前节点指向这个孩子,重复操作直到最后一个字符,将当前节点的isEnd标记为True
- 时间复杂度:$O(m)$
- 空间复杂度:$O(m)$
查找
- 键值为字符串,长度为m
- 从根节点开始,检查是否有指向键值第一个字符的链接
- 如果有,移动到该节点,继续查找下一个字符
- 如果没有
- 还有键的字符剩余,返回False
- 没有键的字符剩余,如果节点isEnd是True,则返回True,否则要查找到键值只是其他单词的前缀,返回False
- 时间复杂度:$O(m)$
- 空间复杂度:$O(1)$
查找前缀
- 与查找相似,不同之处在与,遍历完键值的字符时,不管节点的isEnd是否为True,都返回True
- 键值为字符串,长度为m
- 从根节点开始,检查是否有指向键值第一个字符的链接
- 如果有,移动到该节点,继续查找下一个字符
- 如果没有
- 还有键的字符剩余,返回False
- 没有键的字符剩余,则返回True
- 时间复杂度:$O(m)$
- 空间复杂度:$O(1)$
代码实现
python2,使用节点,beats 19.77%
1 | class TrieNode(object): |
python3,不使用节点,直接使用字典实现,速度更快,beats 98.67%
1 | class Trie: |