Implement a Trie (prefix tree) with `insert(word)`, `search(word)`, and `startsWith(prefix)` methods.
Problem Statement
Implement a Trie (prefix tree) with `insert(word)`, `search(word)`, and `startsWith(prefix)` methods.
Complexity
Time Complexity: -
Space Complexity: -
Hints
š” Hint 1:
A Trie stores characters in tree nodes. Each path from root = a prefix.
š” Hint 2:
Each node has children (a Map/object) and an isEnd flag.
š” Hint 3:
Insert: walk through chars, create nodes. Search: walk and check isEnd. startsWith: walk and check existence.
ā
Solution:
```javascript
class Trie {
constructor() { this.root = {}; }
insert(word) {
let node = this.root;
for (const c of word) { if (!node[c]) node[c] = {}; node = node[c]; }
node.isEnd = true;
}
search(word) {
let node = this.root;
for (const c of word) { if (!node[c]) return false; node = node[c]; }
return node.isEnd === true;
}
startsWith(prefix) {
let node = this.root;
for (const c of prefix) { if (!node[c]) return false; node = node[c]; }
return true;
}
}
```