algoadvance

You are given a list of strings dictionary where each string is a word, and a string sentence containing words separated by spaces. You want to replace all the words in the sentence with the root form of the words found in the dictionary.

If a word has multiple roots in the dictionary, replace it with the shortest one.

Return the sentence with the words replaced.

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"

Example 3:

Input: dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
Output: "a a a a a a a a bbb baba a"

Constraints:

Clarifying Questions

  1. Can a word appear more than once in the sentence?
    • Yes, and it should be replaced every time it appears.
  2. Should we handle punctuation or special characters?
    • No, assume the input is always clean and consists only of lowercase letters and spaces.
  3. Is the dictionary case-sensitive?
    • Yes, everything is in lowercase.

Strategy

  1. Trie Data Structure: Build a Trie from the dictionary to facilitate quick prefix search.
  2. Tokenize Sentence: Split the sentence into words.
  3. Replace Words: For each word in the sentence, find the shortest root in the Trie.
  4. Rebuild Sentence: After replacement, join the words to form the final sentence.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_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_word = True
    
    def search_root(self, word):
        node = self.root
        root = ""
        for char in word:
            if char not in node.children:
                return word
            node = node.children[char]
            root += char
            if node.is_word:
                return root
        return word

def replaceWords(dictionary, sentence):
    trie = Trie()
    for word in dictionary:
        trie.insert(word)
    
    words = sentence.split()
    replaced_sentence = []
    for word in words:
        replaced_sentence.append(trie.search_root(word))
    
    return " ".join(replaced_sentence)

# Example usage:
dictionary = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
print(replaceWords(dictionary, sentence))  # Output: "the cat was rat by the bat"

Time Complexity

  1. Trie Construction: Inserting each dictionary word into the Trie. For n words each of maximum length l, this is O(n * l).
  2. Replacement Search: For each word in the sentence, finding the root using Trie traversal. If m words in the sentence, each of max length l, this is O(m * l).
  3. Total Time Complexity: O(n * l + m * l), where n is the size of the dictionary, m is the number of words in the sentence, and l is the average length of the words.

Try our interview co-pilot at AlgoAdvance.com