Sponsored
Sponsored
Store all roots in a HashSet. This allows for O(1) average time complexity when checking if a root exists. For each word in the sentence, check each prefix to determine if it is a root. As soon as you find a root, replace the word with this root.
Time Complexity: O(N * M), where N is the number of words in the sentence and M is the length of the longest word.
Space Complexity: O(D), where D is the total length of all the roots.
1function replaceWords(dictionary, sentence) {
2 const rootSet = new Set(dictionary);
3 return sentence.split(' ').map(word => {
4 for (let i = 1; i <= word.length; i++) {
5 if (rootSet.has(word.slice(0, i))) {
6 return word.slice(0, i);
7 }
8 }
9 return word;
10 }).join(' ');
11}The JavaScript solution uses a Set to store roots for O(1) lookup time. The sentence is split by spaces, and for each word, we check prefixes. The map function creates a new array with the replacements, and join reconstructs the sentence.
Build a Trie from the given dictionary of roots. A Trie is a tree-like data structure that holds a dynamic set of strings where all keys share a common prefix. For each word in the sentence, traverse through the Trie to find the shortest prefix that matches a segment of the word, if such a prefix exists, it replaces the word.
Time Complexity: O(D + N * K), D is the sum of lengths of all roots, N is the number of words, K is the length of the longest word.
Space Complexity: O(D), for storing the Trie.
1import java.util.*;
2
3
The Java solution involves constructing a Trie from the root words. Each word in the sentence is processed by traversing the Trie to find matching roots. If no root is found, the original word is used.