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 stringword
into the trie.int countWordsEqualTo(String word)
Returns the number of instances of the stringword
in the trie.int countWordsStartingWith(String prefix)
Returns the number of strings in the trie that have the stringprefix
as a prefix.void erase(String word)
Erases the stringword
from the trie.
Example 1:
Input ["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsStartingWith"] [[], ["apple"], ["apple"], ["apple"], ["app"], ["apple"], ["apple"], ["app"], ["apple"], ["app"]] Output [null, null, null, 2, 2, null, 1, 1, null, 0] Explanation Trie trie = new Trie(); trie.insert("apple"); // Inserts "apple". trie.insert("apple"); // Inserts another "apple". trie.countWordsEqualTo("apple"); // There are two instances of "apple" so return 2. trie.countWordsStartingWith("app"); // "app" is a prefix of "apple" so return 2. trie.erase("apple"); // Erases one "apple". trie.countWordsEqualTo("apple"); // Now there is only one instance of "apple" so return 1. trie.countWordsStartingWith("app"); // return 1 trie.erase("apple"); // Erases "apple". Now the trie is empty. trie.countWordsStartingWith("app"); // return 0
Constraints:
1 <= word.length, prefix.length <= 2000
word
andprefix
consist only of lowercase English letters.- At most
3 * 104
calls in total will be made toinsert
,countWordsEqualTo
,countWordsStartingWith
, anderase
. - It is guaranteed that for any function call to
erase
, the stringword
will exist in the trie.
Companies: Docusign
Related Topics:
Hash Table, String, Design, Trie
Similar Questions:
Hints:
- Try to solve the first version first and reuse your code.
- To implement the delete function, you should delete the trie nodes of the word if they are not shared with other words.
- You should keep for each trie node a counter of how many words share this node.
If we don't really delete the node on erase.
// OJ: https://leetcode.com/problems/implement-trie-ii-prefix-tree/
// Author: github.com/lzl124631x
// Time:
// Trie: O(1)
// insert, countWordsEqualTo, countWordsStartingWith, erase: O(W)
// Space: O(1) extra space for all
struct TrieNode {
TrieNode *next[26] = {};
int cnt = 0, prefix = 0;
};
class Trie {
TrieNode root;
TrieNode *find(string s) {
auto n = &root;
for (char c : s) {
if (!n->next[c - 'a'] || n->next[c - 'a']->prefix == 0) return nullptr;
n = n->next[c - 'a'];
}
return n;
}
public:
void insert(string s) {
auto n = &root;
for (char c : s) {
if (!n->next[c - 'a']) n->next[c - 'a'] = new TrieNode();
n = n->next[c - 'a'];
n->prefix++;
}
n->cnt++;
}
int countWordsEqualTo(string s) {
auto n = find(s);
return n ? n->cnt : 0;
}
int countWordsStartingWith(string prefix) {
auto n = find(prefix);
return n ? n->prefix : 0;
}
void erase(string s) {
TrieNode *n = &root;
for (char c : s) {
n = n->next[c - 'a'];
--n->prefix;
}
--n->cnt;
}
};
If we really need to delete the node on erase.
// OJ: https://leetcode.com/problems/implement-trie-ii-prefix-tree
// Author: github.com/lzl124631x
// Time:
// Trie: O(1)
// insert, countWordsEqualTo, countWordsStartingWith, erase: O(W)
// Space: O(1) extra space for all
struct TrieNode {
TrieNode *next[26] = {};
int cnt = 0, prefix = 0;
};
class Trie {
TrieNode root;
TrieNode *find(string s) {
auto n = &root;
for (char c : s) {
if (!n->next[c - 'a']) return nullptr;
n = n->next[c - 'a'];
}
return n;
}
public:
void insert(string s) {
auto n = &root;
for (char c : s) {
if (!n->next[c - 'a']) n->next[c - 'a'] = new TrieNode();
n = n->next[c - 'a'];
n->prefix++;
}
n->cnt++;
}
int countWordsEqualTo(string s) {
auto n = find(s);
return n ? n->cnt : 0;
}
int countWordsStartingWith(string prefix) {
auto n = find(prefix);
return n ? n->prefix : 0;
}
void erase(string s) {
TrieNode *n = &root, *next = n->next[s[0] - 'a'];
for (int N = s.size(), i = 0; i < N; ++i) {
auto prev = n;
n = next;
if (i + 1 < N) next = n->next[s[i + 1] - 'a'];
if (--n->prefix == 0) {
if (prev) prev->next[s[i] - 'a'] = nullptr;
delete n;
n = nullptr;
}
}
if (n) --n->cnt;
}
};