[LeetCode] 208. Implement Trie (Prefix Tree)

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 string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return True

Constraints:

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 104 calls in total will be made to insert, search, and startsWith.

实现 Trie (前缀树)。

题意基本跟211题一致，需要实现几个字典树的函数。思路是需要自己实现一个 TrieNode 的类然后遍历单词的每个字母。这就是模板题，需要背下来。

时间O(n), n是需要遍历的单词的长度

空间O(num of TrieNode * 26) = O(num of words * word.length() * 26)

Java实现

 1 class Trie {
 2     class Node {
 3         Node[] children;
 4         boolean isEnd;
 5         String word;
 6 
 7         public Node() {
 8             children = new Node[26];
 9             isEnd = false;
10             word = "";
11         }
12     }
13 
14     Node root;
15 
16     /** Initialize your data structure here. */
17     public Trie() {
18         root = new Node();
19     }
20 
21     /** Inserts a word into the trie. */
22     public void insert(String word) {
23         Node node = root;
24         for (int i = 0; i < word.length(); i++) {
25             int j = word.charAt(i) - 'a';
26             if (node.children[j] == null) {
27                 node.children[j] = new Node();
28             }
29             node = node.children[j];
30         }
31         node.isEnd = true;
32     }
33 
34     /** Returns if the word is in the trie. */
35     public boolean search(String word) {
36         Node node = root;
37         for (int i = 0; i < word.length(); i++) {
38             int j = word.charAt(i) - 'a';
39             if (node.children[j] == null) {
40                 return false;
41             }
42             node = node.children[j];
43         }
44         return node.isEnd;
45     }
46 
47     /** Returns if there is any word in the trie that starts with the given prefix. */
48     public boolean startsWith(String prefix) {
49         Node node = root;
50         for (int i = 0; i < prefix.length(); i++) {
51             int j = prefix.charAt(i) - 'a';
52             if (node.children[j] == null) {
53                 return false;
54             }
55             node = node.children[j];
56         }
57         return true;
58     }
59 }
60 
61 /**
62  * Your Trie object will be instantiated and called as such:
63  * Trie obj = new Trie();
64  * obj.insert(word);
65  * boolean param_2 = obj.search(word);
66  * boolean param_3 = obj.startsWith(prefix);
67  */

LeetCode 题目总结