Trie
June 24, 2025
04:33 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
Solution
1class TrieNode {
2 children: Map<string, TrieNode>;
3 is_word: boolean;
4 constructor() {
5 this.children = new Map();
6 this.is_word = false;
7 }
8}
9export default class Trie {
10 root: TrieNode;
11 constructor() {
12 this.root = new TrieNode();
13 }
14 public insert(word: string): void {
15 let node = this.root;
16 for (const char of word) {
17 if (!node.children.has(char)) node.children.set(char, new TrieNode());
18 node = node.children.get(char)!;
19 }
20 node.is_word = true;
21 }
22
23 public search(word: string): boolean {
24 let node = this.root;
25 for (const char of word) {
26 if (!node.children.has(char)) {
27 return false;
28 }
29 node = node.children.get(char)!;
30 }
31 return node.is_word;
32 }
33
34 public startsWith(prefix: string): boolean {
35 let node = this.root;
36 for (const char of prefix) {
37 if (!node.children.has(char)) {
38 return false;
39 }
40 node = node.children.get(char)!;
41 }
42 return true;
43 }
44}