|
1 | | - |
2 | 1 | // #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Hash_Table #Design #Trie |
3 | 2 | // #Level_2_Day_16_Design #Udemy_Trie_and_Heap |
4 | 3 | // #Big_O_Time_O(word.length())_or_O(prefix.length())_Space_O(N) |
5 | 4 | // #2024_12_17_Time_39_ms_(93.97%)_Space_66.4_MB_(88.79%) |
6 | 5 |
|
7 | 6 | varTrie=function(){ |
8 | | -this.root={}// Initialize root node as an empty object |
9 | | -} |
| 7 | +this.root={}; |
| 8 | +}; |
10 | 9 |
|
11 | 10 | /** |
12 | 11 | *@param {string} word |
13 | 12 | *@return {void} |
14 | 13 | */ |
15 | 14 | Trie.prototype.insert=function(word){ |
16 | | -letnode=this.root |
17 | | -for(leti=0;i<word.length;i++){ |
18 | | -constchar=word[i] |
| 15 | +letnode=this.root; |
| 16 | +for(constcharofword){ |
19 | 17 | if(!node[char]){ |
20 | | -node[char]={}// Create a new node if it doesn't exist |
| 18 | +node[char]={}; |
21 | 19 | } |
22 | | -node=node[char]// Move to the next node |
| 20 | +node=node[char]; |
23 | 21 | } |
24 | | -node.isWord=true// Mark the node as a word endpoint |
| 22 | +node.isWord=true; |
25 | 23 | }; |
26 | 24 |
|
27 | 25 | /** |
28 | 26 | *@param {string} word |
29 | 27 | *@return {boolean} |
30 | 28 | */ |
31 | 29 | Trie.prototype.search=function(word){ |
32 | | -letnode=this.root |
33 | | -for(leti=0;i<word.length;i++){ |
34 | | -constchar=word[i] |
| 30 | +letnode=this.root; |
| 31 | +for(constcharofword){ |
35 | 32 | if(!node[char]){ |
36 | | -returnfalse// Word doesn't exist |
| 33 | +returnfalse; |
37 | 34 | } |
38 | | -node=node[char]// Move to the next node |
| 35 | +node=node[char]; |
39 | 36 | } |
40 | | -returnnode.isWord===true// Return true if it's a complete word |
| 37 | +returnnode.isWord===true; |
41 | 38 | }; |
42 | 39 |
|
43 | 40 | /** |
44 | 41 | *@param {string} prefix |
45 | 42 | *@return {boolean} |
46 | 43 | */ |
47 | 44 | Trie.prototype.startsWith=function(prefix){ |
48 | | -letnode=this.root |
49 | | -for(leti=0;i<prefix.length;i++){ |
50 | | -constchar=prefix[i] |
| 45 | +letnode=this.root; |
| 46 | +for(constcharofprefix){ |
51 | 47 | if(!node[char]){ |
52 | | -returnfalse// Prefix doesn't exist |
| 48 | +returnfalse; |
53 | 49 | } |
54 | | -node=node[char]// Move to the next node |
| 50 | +node=node[char]; |
55 | 51 | } |
56 | | -returntrue// Return true if prefix exists |
| 52 | +returntrue; |
57 | 53 | }; |
58 | 54 |
|
59 | 55 | /** |
|