648. Replace Words
Tags:
Medium
Skills:
Trie
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Approach - Trie
Time and space complexity
Solution
1class TrieNode {
2 children: Map<string, TrieNode>;
3 end_word: boolean;
4 constructor() {
5 this.children = new Map();
6 this.end_word = false;
7 }
8}
9
10class Trie {
11 root: TrieNode;
12 constructor() {
13 this.root = new TrieNode();
14 }
15
16 insert(word: string): void {
17 let node = this.root;
18 for (let char of word) {
19 if (!node.children.has(char)) {
20 node.children.set(char, new TrieNode())
21 }
22 node = node.children.get(char);
23 }
24 node.end_word = true;
25 }
26
27 search_prefix(word: string): string {
28 let node = this.root;
29 let prefix = "";
30 for (const char of word) {
31 if (!node.children.has(char)) {
32 return word;
33 }
34
35 prefix += char;
36 node = node.children.get(char);
37 if (node.end_word) {
38 return prefix;
39 }
40 }
41 return word;
42 }
43}
44
45function replaceWords(dictionary: string[], sentence: string): string {
46 const trie = new Trie();
47 for (const root of dictionary) {
48 trie.insert(root);
49 }
50 const words = sentence.split(" ");
51 for (let i = 0; i < words.length; i++) {
52 words[i] = trie.search_prefix(words[i]);
53 }
54
55 return words.join(" ");
56};