208. Implement Trie (Prefix Tree)
Question
A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie()
Initializes the trie object.
void insert(String word)
Inserts the stringword
into the trie.
boolean search(String word)
Returnstrue
if the stringword
is in the trie (i.e., was inserted before), andfalse
otherwise.
boolean startsWith(String prefix)
Returnstrue
if there is a previously inserted stringword
that has the prefixprefix
, andfalse
otherwise.
Solution
参考:实现 Trie :「二维数组」&「TrieNode」方式
前缀树,字典树结构实现。
前缀树 Trie
前缀树结构用“边”记录有无字符,用“点”记录单词结尾以及后续的字符串字符。
root节点记录字典的根节点。
TrieNode节点
用TrieNode节点实现前缀树。
真值end记录是否为字符串的结尾,创建时默认为false。
数组TrieNode[] children记录子节点。
insert()方法
从根节点root开始,遍历字符串。
如果对应的子节点位置为空,则创建新的TrieNode节点。
向下移动当前节点。
将最后一个节点设置为end,使得整个字符串被字典记录。
search()方法
从根节点root开始,遍历字符串。
如果子节点位置为空,则这个字符串不在字典中,返回false。
否则向下移动当前节点。
遍历完毕,如果当前节点的end为true,则存在该字符串,返回true。
startsWith()方法
从根节点root开始,遍历前缀字符串。
如果子节点位置为空,则这个前缀不在字典中,返回false。
否则向下移动当前节点。
最后返回true。
Code
1 | class Trie { |