阅读原文
https://blog.baozitraining.org/2019/04/leetcode-solution-208-implement-trie.html
Implement a trie with insert
, search
, and startsWith
methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
a-z
.Problem link
You can find the detailed video tutorial here
Trie (prefix tree) is a very common data structure that appears very often in interviews. I used to get asked Trie at Fitbit, Snap and Google back in the days. I highly recommend you brush up on this basic data structure. Please refer to this Baozi Training Blog for a modified version explained: https://blog.baozitraining.org/2019/03/leetcode-solution-211-add-and-search.html Leetcode actually did a great job explaining this problem. Feel free to download the explanation here (all credit and copyright goes to leetcode, obviously)
public class TrieNode {
public Character letter = null;
// a boolean to indicate if this node is end of a word, sometimes we want to match word exactly, not just prefix
public boolean isEnd = false;
public Map<Character, TrieNode> children = null;
// Initialize your data structure here.
public TrieNode() {
this.children = new HashMap<Character, TrieNode>();
}
}
public TrieNode root;
public ImplementTrie() {
// This root node essentially is a dummy root
this.root = new TrieNode();
}
// This is my fitbit onsite version, looks cool
public void insert(String word) {
if (word == null || word.length() == 0) {
return;
}
TrieNode cur = this.root;
int i = 0;
while (i < word.length()) {
char c = word.charAt(i);
if (!cur.children.containsKey(c)) {
cur.children.put(c, new TrieNode());
}
cur = cur.children.get(c);
i++;
}
cur.isEnd = true;
}
// Returns if the word is in the trie, it has to be the exact word
public boolean search(String word) {
if (word == null || word.length() == 0) {
return false;
}
int i = 0;
TrieNode cur = this.root;
while (i < word.length()) {
char c = word.charAt(i);
if (!cur.children.containsKey(c)) {
return false;
}
cur = cur.children.get(c);
i++;
}
return cur.isEnd;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if (prefix == null || prefix.length() == 0) {
return false;
}
int i = 0;
TrieNode cur = this.root;
// Nice, this means if prefix is empty, it can match everything, if it's " " space, then it won't match unless there is a space
while (i < prefix.length()) {
char c = prefix.charAt(i);
if (!cur.children.containsKey(c)) {
return false;
}
cur = cur.children.get(c);
i++;
}
return true;
}
Time Complexity: assuming N is the word length, insert O(N), search O(N), startWith O(N) Space Complexity: assuming N is the word length, insert O(N), search O(1), startWith O(1)