LeetCode 1804: Implement Trie II (Prefix Tree)
LeetCode 1804 Solution Explanation
Explanation
A trie (pronounced "try") or prefix tree is a tree data structure that is used to store a dynamic set of strings. In this problem, we are required to implement a Trie II class that supports the following operations:
insert(word: str): Inserts a word into the trie.countWordsEqualTo(word: str): Returns the number of words in the trie that are equal to the given word.countWordsStartingWith(prefix: str): Returns the number of words in the trie that have the given prefix.
To implement this, we can use a TrieNode class to represent each node in the trie. Each node will have a map of character to the next TrieNode, a count of words that end at that node, and a count of words that start with the prefix leading to that node.
LeetCode 1804 Solutions in Java, C++, Python
class TrieNode {
Map<Character, TrieNode> children;
int countEndsHere;
int countStartsWith;
public TrieNode() {
children = new HashMap<>();
countEndsHere = 0;
countStartsWith = 0;
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
curr.countStartsWith++;
curr.children.putIfAbsent(c, new TrieNode());
curr = curr.children.get(c);
}
curr.countEndsHere++;
}
public int countWordsEqualTo(String word) {
TrieNode curr = root;
for (char c : word.toCharArray()) {
if (!curr.children.containsKey(c)) {
return 0;
}
curr = curr.children.get(c);
}
return curr.countEndsHere;
}
public int countWordsStartingWith(String prefix) {
TrieNode curr = root;
for (char c : prefix.toCharArray()) {
if (!curr.children.containsKey(c)) {
return 0;
}
curr = curr.children.get(c);
}
return curr.countStartsWith;
}
}Interactive Code Editor for LeetCode 1804
Improve Your LeetCode 1804 Solution
Use the editor below to refine the provided solution for LeetCode 1804. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...