## DEV Community

Abhishek Chaudhary

Posted on

# 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:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"

Example 2:

Output: "a a b c"

Constraints:

• `1 <= dictionary.length <= 1000`
• `1 <= dictionary[i].length <= 100`
• `dictionary[i]` consists of only lower-case letters.
• `1 <= sentence.length <= 106`
• `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]`
• Every two consecutive words in `sentence` will be separated by exactly one space.
• `sentence` does not have leading or trailing spaces.

SOLUTION:

``````class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
dictionary = set(dictionary)
lens = sorted([len(w) for w in dictionary])
words = sentence.split()
op = []
for w in words:
found = False
for l in lens:
if w[:l] in dictionary:
op.append(w[:l])
found = True
break