https://leetcode.com/problems/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.
- code
class Trie {
class TrieNode {
public boolean isWord;
public Map<Character, TrieNode> childrenMap = new HashMap<>();
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode cur = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(cur.childrenMap.get(c) == null){
// insert a new node if the path does not exist
cur.childrenMap.put(c, new TrieNode());
}
cur = cur.childrenMap.get(c);
}
cur.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode cur = root;
for(int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if(cur.childrenMap.get(c) == null) {
return false;
}
cur = cur.childrenMap.get(c);
}
return cur.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode cur = root;
for(int i = 0;i < prefix.length(); i++){
char c = prefix.charAt(i);
if(cur.childrenMap.get(c) == null) {
return false;
}
cur = cur.childrenMap.get(c);
}
return true;
}
}
- code
class Trie:
def __init__(self):
self.m = {}
def insert(self, word: str) -> None:
node = self.m
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['$'] = True
def searchPrefix(self, prefix: str):
node = self.m
for c in prefix:
if c not in node:
return False
node = node[c]
return node
def search(self, word: str) -> bool:
node = self.searchPrefix(word)
return False if node is False else '$' in node
def startsWith(self, prefix: str) -> bool:
node = self.searchPrefix(prefix)
return False if node is False else True
If the longest length of the word is N, the height of Trie will be N + 1. Therefore, the time complexity of all insert, search and startsWith methods will be O(N).
If we have M words to insert in total and the length of words is at most N, there will be at most M * N nodes in the worst case (any two words don’t have a common prefix).Let’s assume that there are maximum K different characters (K is equal to 26 in this problem, but might differs in different cases). So each node will maintain a map whose size is at most K.Therefore, the space complexity will be O(M*N*K).
It seems that Trie is really space consuming, however, the real space complexity of Trie is much smaller than our estimation, especially when the distribution of words is dense.