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.
1def replaceWords(dictionary, sentence):
2 rootSet = set(dictionary)
3 def replace(word):
4 for i in range(1, len(word) + 1):
5 if word[:i] in rootSet:
6 return word[:i]
7 return word
8 return ' '.join(map(replace, sentence.split()))This solution creates a set from the given dictionary containing root words. It then splits the sentence into words and attempts to replace each word with its shortest root using the replace() function. For each word, the function checks successive prefixes and returns the prefix (root) if it exists in the set. The replaced words are then joined back into a sentence and returned.
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.