Leetcode 208 solution: Implement Trie (Prefix Tree)

https://blog.baozitraining.org/2019/04/leetcode-solution-208-implement-trie.html

Problem Statement

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:

• You may assume that all inputs are consist of lowercase letters `a-z`.
• All inputs are guaranteed to be non-empty strings.

Video Tutorial

You can find the detailed video tutorial here

Thought Process

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)

References

• Leetcode official solution

0 条评论