Implement Trie ll
Implement Trie ll is a medium tries problem solved with the basics pattern.
The best approach, optimal (trie with prefix and end counters), runs in O(L) per operation time and O(total characters · 26) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from hash map of word counts up.
Problem
Implement a trie that also counts: insert(word), countWordsEqualTo(word), countWordsStartingWith(prefix) and erase(word) (remove one copy). Duplicate words are allowed.
Examples
Example 1
- Input
insert(apple), insert(apple), insert(apps), countWordsEqualTo(apple), countWordsStartingWith(app), erase(apple), countWordsEqualTo(apple)- Output
2, 3, 1
Constraints
- Lowercase words; erase is only called on words that exist.
- Up to
3 * 10^4operations.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (1 examples, or your own). Submit also runs 8 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Hash map of word counts | O(n · L) for prefix counts | O(total characters) |
| Optimal (trie with prefix and end counters) | O(L) per operation | O(total characters · 26) |
1Hash map of word counts
O(n · L) for prefix countsO(total characters)Keep a map word → count. Counting prefixes scans every word.
- insert/erase adjust the count.
- countWordsStartingWith sums counts of words with the prefix.
class Trie {
private final Map<String, Integer> count = new HashMap<>();
public void insert(String word) { count.merge(word, 1, Integer::sum); }
public int countWordsEqualTo(String word) { return count.getOrDefault(word, 0); }
public int countWordsStartingWith(String prefix) {
int total = 0;
for (Map.Entry<String, Integer> e : count.entrySet())
if (e.getKey().startsWith(prefix)) total += e.getValue();
return total;
}
public void erase(String word) {
if (count.merge(word, -1, Integer::sum) == 0) count.remove(word);
}
}class Trie:
def __init__(self):
self.count: Dict[str, int] = {}
def insert(self, word: str) -> None:
self.count[word] = self.count.get(word, 0) + 1
def countWordsEqualTo(self, word: str) -> int:
return self.count.get(word, 0)
def countWordsStartingWith(self, prefix: str) -> int:
total = 0
for key, value in self.count.items():
if key.startswith(prefix):
total += value
return total
def erase(self, word: str) -> None:
self.count[word] -= 1
if self.count[word] == 0:
del self.count[word]class Trie {
unordered_map<string, int> count;
public:
void insert(string word) { count[word]++; }
int countWordsEqualTo(string word) {
auto it = count.find(word);
return it == count.end() ? 0 : it->second;
}
int countWordsStartingWith(string prefix) {
int total = 0;
for (auto& e : count)
if (e.first.compare(0, prefix.size(), prefix) == 0) total += e.second;
return total;
}
void erase(string word) {
if (--count[word] == 0) count.erase(word);
}
};class Trie {
constructor() { this.count = new Map(); }
insert(word) { this.count.set(word, (this.count.get(word) || 0) + 1); }
countWordsEqualTo(word) { return this.count.get(word) || 0; }
countWordsStartingWith(prefix) {
let total = 0;
for (const [key, value] of this.count)
if (key.startsWith(prefix)) total += value;
return total;
}
erase(word) {
const left = this.count.get(word) - 1;
if (left === 0) this.count.delete(word);
else this.count.set(word, left);
}
}2Optimal (trie with prefix and end counters)
O(L) per operationO(total characters · 26)Each node stores prefix, the number of words passing through it, and end, the number of words ending there. insert increments along the path, erase decrements along it, and both counts are read at the last node of the walk.
- insert: for each char, create if missing, move, prefix++. Then end++.
- countWordsEqualTo: walk; return end or 0.
- countWordsStartingWith: walk; return prefix or 0.
- erase: walk, prefix-- at each node; end-- at the last.
class Trie {
private static class Node {
Node[] next = new Node[26];
int prefix, end;
}
private final Node root = new Node();
public void insert(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
cur = cur.next[c - 'a'];
cur.prefix++;
}
cur.end++;
}
public int countWordsEqualTo(String word) {
Node n = walk(word);
return n == null ? 0 : n.end;
}
public int countWordsStartingWith(String prefix) {
Node n = walk(prefix);
return n == null ? 0 : n.prefix;
}
public void erase(String word) {
Node cur = root;
for (char c : word.toCharArray()) {
cur = cur.next[c - 'a'];
cur.prefix--;
}
cur.end--;
}
private Node walk(String s) {
Node cur = root;
for (char c : s.toCharArray()) {
cur = cur.next[c - 'a'];
if (cur == null) return null;
}
return cur;
}
}class Node:
def __init__(self):
self.next: List[Optional["Node"]] = [None] * 26
self.prefix = 0
self.end = 0
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> None:
cur = self.root
for c in word:
i = ord(c) - ord('a')
if cur.next[i] is None:
cur.next[i] = Node()
cur = cur.next[i]
cur.prefix += 1
cur.end += 1
def countWordsEqualTo(self, word: str) -> int:
n = self.walk(word)
return 0 if n is None else n.end
def countWordsStartingWith(self, prefix: str) -> int:
n = self.walk(prefix)
return 0 if n is None else n.prefix
def erase(self, word: str) -> None:
cur = self.root
for c in word:
cur = cur.next[ord(c) - ord('a')]
cur.prefix -= 1
cur.end -= 1
def walk(self, s: str) -> Optional[Node]:
cur = self.root
for c in s:
cur = cur.next[ord(c) - ord('a')]
if cur is None:
return None
return curclass Trie {
struct Node {
Node* next[26] = {};
int prefix = 0, end = 0;
};
Node* root = new Node();
public:
void insert(string word) {
Node* cur = root;
for (char c : word) {
if (cur->next[c - 'a'] == nullptr) cur->next[c - 'a'] = new Node();
cur = cur->next[c - 'a'];
cur->prefix++;
}
cur->end++;
}
int countWordsEqualTo(string word) {
Node* n = walk(word);
return n == nullptr ? 0 : n->end;
}
int countWordsStartingWith(string prefix) {
Node* n = walk(prefix);
return n == nullptr ? 0 : n->prefix;
}
void erase(string word) {
Node* cur = root;
for (char c : word) {
cur = cur->next[c - 'a'];
cur->prefix--;
}
cur->end--;
}
private:
Node* walk(const string& s) {
Node* cur = root;
for (char c : s) {
cur = cur->next[c - 'a'];
if (cur == nullptr) return nullptr;
}
return cur;
}
};class Node {
constructor() {
this.next = new Array(26).fill(null);
this.prefix = 0;
this.end = 0;
}
}
class Trie {
constructor() { this.root = new Node(); }
insert(word) {
let cur = this.root;
for (let i = 0; i < word.length; i++) {
const c = word.charCodeAt(i) - 97;
if (cur.next[c] === null) cur.next[c] = new Node();
cur = cur.next[c];
cur.prefix++;
}
cur.end++;
}
countWordsEqualTo(word) {
const n = this.walk(word);
return n === null ? 0 : n.end;
}
countWordsStartingWith(prefix) {
const n = this.walk(prefix);
return n === null ? 0 : n.prefix;
}
erase(word) {
let cur = this.root;
for (let i = 0; i < word.length; i++) {
cur = cur.next[word.charCodeAt(i) - 97];
cur.prefix--;
}
cur.end--;
}
walk(s) {
let cur = this.root;
for (let i = 0; i < s.length; i++) {
cur = cur.next[s.charCodeAt(i) - 97];
if (cur === null) return null;
}
return cur;
}
}Edge cases to test
- Inserting the same word several times
- Erasing one copy of a duplicated word
Hints
Hint 1
Store two counters in every node: how many words pass through it (prefix count) and how many words end at it.
FAQ
What is the best time complexity for Implement Trie ll?
Optimal (trie with prefix and end counters) runs in O(L) per operation time and O(total characters · 26) extra space.
Which pattern does Implement Trie ll use?
It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie (Prefix Tree), Design In-Memory File System, Design Search Autocomplete System.
Is there a brute force solution for Implement Trie ll?
Yes. Hash map of word counts takes O(n · L) for prefix counts time and O(total characters) space. Keep a map word → count.
Which edge cases should I test for Implement Trie ll?
Inserting the same word several times; Erasing one copy of a duplicated word.