Replace_Words.py

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

# Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
# 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.


class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        # get all the words in a list
        split_words = sentence.split(' ')
        # go through the roots and replace any successor word with the root from the list of words
        for root in dictionary:
            for i in range(len(split_words)):
                # if the root is in the word as a substring
                if root in split_words[i]:
                    # if the substring is at the beginning of the word
                    if root == split_words[i][:len(root)]:
                        # swap
                        split_words[i] = root
        # return the string joined from the modified list of words
        return ' '.join(split_words)