Replace Words - Leetcode Solution

The Replace Words problem on LeetCode asks for a way to replace every word in a sentence with the shortest possible root word that appears in a given dictionary.

The algorithm to solve this problem can be done using a Trie data structure to model the dictionary of root words, and then traversing the sentence and replacing each word with the shortest root word that appears in the Trie.

Here is a step-by-step solution to the Replace Words problem:

Step 1: Create a Trie data structure to store the dictionary of root words.

To create the Trie, iterate through the dictionary of root words and insert each word into the Trie. For each word, follow the path in the Trie corresponding to the letters in the word, and at the last node of the path, mark the node as a leaf node and store the word as the value of the node. This will allow us to easily find the shortest root word that a given word prefixes.

Step 2: Traverse the sentence and replace each word with the shortest root word that appears in the Trie.

To do this, split the sentence into individual words. For each word, follow the path in the Trie corresponding to the letters in the word. If at any point there is no path for the next letter, or if the current node is not a leaf node, then there is no root word that the word prefixes in the dictionary. In this case, keep the original word in the sentence. Otherwise, replace the word in the sentence with the value of the node (which is the shortest root word that appears in the dictionary).

Step 3: Return the modified sentence.

The final step is to return the modified sentence after replacing each word with the shortest root word that appears in the dictionary.

Here is an example implementation of the above algorithm in Python:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False
        self.word = ''

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_word = True
        node.word = word

    def shortest_prefix(self, word):
        node = self.root
        prefix = ''
        for c in word:
            if c not in node.children or node.is_word:
                break
            prefix += c
            node = node.children[c]
        return node.word if node.is_word else word

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        trie = Trie()
        for word in dictionary:
            trie.insert(word)

        words = sentence.split()
        for i in range(len(words)):
            words[i] = trie.shortest_prefix(words[i])

        return ' '.join(words)

In the above code, we first define the TrieNode and Trie classes to create and traverse a Trie data structure. Then, in the replaceWords function, we create an instance of the Trie class and insert all the words from the dictionary into the Trie.

Next, we split the sentence into individual words, and for each word, we find the shortest prefix in the dictionary using the shortest_prefix function. If there is no prefix in the dictionary, we keep the original word.

Finally, we join all the modified words back together into a sentence and return it as the result.

Overall, the time complexity of this algorithm is O(NM) where N is the number of words in the sentence and M is the maximum length of a word in the dictionary. This is because we need to traverse the Trie for each word in the sentence, and the worst case scenario is when the Trie has depth M and each word in the sentence is also of length M. The space complexity of the algorithm is also O(NM) because we need to store the Trie.

1