Implement a trie (prefix tree)
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.
class Trie {
constructor() {
this.root = {};
}
insert(word) {
let node = this.root;
for (let c of word) {
if (node[c] == null) node[c] = {};
node = node[c];
}
node.isWord = true;
}
traverse(word) {
let node = this.root;
for (let c of word) {
node = node[c];
if (node == null) return null;
}
return node;
}
search(word) {
const node = this.traverse(word);
return node != null && node.isWord === true;
}
startsWith(prefix) {
return this.traverse(prefix) != null;
}
}Related Problems
Given the head of a linked list, remove the nth node from the end of the list and return its head.
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.
The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).