# Replace Words

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 successor. For example, when the root `"an"` is followed by the successor word `"other"`, we can form a new word `"another"`.

Given a `dictionary` consisting of many roots and a `sentence` consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor 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:

Example 2:

Example 3:

Example 4:

Example 5:

Constraints:

• `1 <= dictionary.length <= 1000`
• `1 <= dictionary[i].length <= 100`
• `dictionary[i]` consists of only lower-case letters.
• `1 <= sentence.length <= 10^6`
• `sentence` consists of only lower-case letters and spaces.
• The number of words in `sentence` is in the range `[1, 1000]`
• The length of each word in `sentence` is in the range `[1, 1000]`
• Each two consecutive words in `sentence` will be separated by exactly one space.
• `sentence` does not have leading or trailing spaces.

Algorithm

Store all the `roots` in a HashSet data structure. Then for each word, look at successive prefixes of that word. If you find a prefix that is a root, replace the word with that prefix. Otherwise, the prefix will just be the word itself, and we should add that to the final sentence answer.

Complexity Analysis

• Time Complexity : O(∑wi2​) where wi​ is the length of the i-th word. We might check every prefix, the i-th of which is O(wi2​) work.
• Space Complexity : O(N) where NN is the length of our sentence; the space used by `rootset`.

Full Stack Programmer, love to solve problem’s during free time.

## More from Jaydeep

Full Stack Programmer, love to solve problem’s during free time.