We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Replace Words

Difficulty: Medium

Problem Description

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.

Key Insights

  • Each derivative word can be formed by appending a suffix to a root.
  • We need to identify the shortest root for each word in the sentence that can be replaced.
  • A Trie data structure is useful to efficiently check for roots while processing each word in the sentence.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of words in the sentence and m is the average length of the words in the dictionary. Space Complexity: O(k) where k is the total number of characters in the dictionary.

Solution

To solve this problem, we can utilize a Trie (prefix tree) to store all the roots from the dictionary. This allows us to efficiently check each word in the sentence for potential replacements. The steps are as follows:

  1. Insert all roots into the Trie.
  2. For each word in the sentence, traverse the Trie to find the shortest root that can replace it.
  3. If a root is found, replace the word in the sentence; otherwise, keep the original word.
  4. Finally, join the processed words to form the resulting sentence.

Code Solutions

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True
    
    def search_shortest_root(self, word):
        node = self.root
        root = ""
        for char in word:
            if char in node.children:
                root += char
                node = node.children[char]
                if node.is_end_of_word:
                    return root
            else:
                break
        return None

def replaceWords(dictionary, sentence):
    trie = Trie()
    for root in dictionary:
        trie.insert(root)
    
    words = sentence.split()
    for i in range(len(words)):
        shortest_root = trie.search_shortest_root(words[i])
        if shortest_root:
            words[i] = shortest_root
    
    return " ".join(words)
← Back to All Questions