In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".
Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.
Return the sentence after the replacement.
Example 1:
Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery" Output: "the cat was rat by the bat"
Example 2:
Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs" Output: "a a b c"
Constraints:
1 <= dictionary.length <= 10001 <= dictionary[i].length <= 100dictionary[i] consists of only lower-case letters.1 <= sentence.length <= 106sentence consists of only lower-case letters and spaces.sentence is in the range [1, 1000]sentence is in the range [1, 1000]sentence will be separated by exactly one space.sentence does not have leading or trailing spaces.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.
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.
JavaScript
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.
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.
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.
C++
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.
| Approach | Complexity |
|---|---|
| Using HashSet for Quick Search | Time Complexity: O(N * M), where N is the number of words in the sentence and M is the length of the longest word. |
| Using Trie for Prefix Search | 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. |
Longest Repeating Character Replacement - Leetcode 424 - Python • NeetCode • 599,364 views views
Watch 9 more video solutions →Practice Replace Words with our built-in code editor and test cases.
Practice on FleetCode