题目描述
Trie (发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。
请你实现 Trie 类:
Trie()
初始化前缀树对象。
void insert(String word)
向前缀树中插入字符串 word
。
boolean search(String word)
如果字符串 word
在前缀树中,返回 true
(即,在检索之前已经插入);否则,返回 false
。
boolean startsWith(String prefix)
如果之前已经插入的字符串 word
的前缀之一为 prefix
,返回 true
;否则,返回 false
。
示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| 输入 ["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
次
解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63
| class Trie { private Trie[] children; private boolean isEnd;
public Trie() { children=new Trie[26]; isEnd=false; }
public void insert(String word) { Trie node=this; for (int i = 0; i < word.length(); i++) { char ch=word.charAt(i); int index=ch-'a'; if (node.children[index]==null){ node.children[index]=new Trie(); } node=node.children[index]; } node.isEnd=true; }
public boolean search(String word) { Trie node=this; for (int i = 0; i < word.length(); i++) { node=node.children[word.charAt(i)-'a']; if (node==null){ return false; } } return node.isEnd; }
public boolean startsWith(String prefix) { Trie node=this; for (int i = 0; i < prefix.length(); i++) { node=node.children[prefix.charAt(i)-'a']; if (node==null){ return false; } } return true; } }
|
来源:力扣(LeetCode)
链接:208. 实现 Trie (前缀树) - 力扣(LeetCode)