LeetCode Solutions Blog

Replace Words

Number: 648

Difficulty: Medium

Paid? No

Problem Description

Given a dictionary of roots and a sentence, replace each word in the sentence with the shortest root from the dictionary that is a prefix of the word. If a word has no root prefix in the dictionary, keep it unchanged.

Key Insights

A Trie (prefix tree) is an ideal data structure to quickly find the shortest prefix match.
Insert all dictionary words into the Trie.
For each word in the sentence, traverse the Trie character by character until a complete root is found or no further matching branch exists.
Using a space split for the sentence enables individual word processing.

Space and Time Complexity

Time Complexity: O(m + n * l) where m is the total number of characters in all dictionary roots, n is the number of words in the sentence, and l is the average length of a word. Space Complexity: O(m) for storing the Trie.

Solution

We insert each root from the dictionary into a Trie. For each word in the sentence, we iterate character by character checking for a matching prefix. Once we find a node that marks the end of a dictionary word (a valid root), we replace the current word with that root. If no such prefix exists for a word, we leave it unchanged. This approach optimally leverages the Trie to quickly determine prefix matches and minimizes unnecessary comparisons.

Code Solutions

# Define a Trie Node class
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

# Define a Trie class to insert roots and search for shortest prefix
class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    # Insert a word into the Trie
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    # Search for the shortest prefix of the word that is in the Trie
    def search_shortest_prefix(self, word: str) -> str:
        node = self.root
        prefix = ""
        for char in word:
            if char not in node.children:
                break
            node = node.children[char]
            prefix += char
            if node.is_end:
                return prefix
        return word

# Main function to replace words in the sentence
def replaceWords(dictionary: list, sentence: str) -> str:
    trie = Trie()
    # Insert all roots from dictionary into the Trie
    for root in dictionary:
        trie.insert(root)
    
    words = sentence.split()
    result = []
    # Process each word in the sentence
    for word in words:
        result.append(trie.search_shortest_prefix(word))
    return " ".join(result)

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