Domain 2MediumCORE

Replace Words

We are given a list of root words and a sentence composed of space-separated words. The goal is to iterate through every word in the sentence and check if it starts with any root from the dictionary. If it does, we replace the entire word with that root. Crucially, if multiple roots match (e.g., 'a' and 'aa' both match 'another'), we must choose the one with the shortest length.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Trie

648. Replace Words

Model: qwen3.5:9b
Topics: Hash Table,Trie
FAANG asked: 0
Acceptance rate: 59.0%


Problem Breakdown

We are given a list of root words and a sentence composed of space-separated words. The goal is to iterate through every word in the sentence and check if it starts with any root from the dictionary. If it does, we replace the entire word with that root. Crucially, if multiple roots match (e.g., “a” and “aa” both match “another”), we must choose the one with the shortest length.

Inputs:

  • dictionary: List of strings (roots).
  • sentence: String containing words separated by single spaces.

Outputs:

  • Modified sentence string where successors are replaced by their shortest matching root.

Implicit Constraints & Edge Cases:

  • A word might not match any root at all; it remains unchanged.
  • A word might be shorter than the longest possible root (handled naturally by traversal).
  • Multiple roots can share prefixes (e.g., “cat”, “cattle”). We must stop at the first valid root found during traversal to ensure we pick the shortest one.
  • The sentence length is large (10610^6), so efficiency in string processing and lookups is critical.

Intuition

A naive brute-force approach would be: for every word in the sentence, iterate through every root in the dictionary and check if the root is a prefix of the word using startswith.

  • Complexity: O(N⋅M⋅L)O(N \cdot M \cdot L), where NN is words in sentence, MM is roots in dictionary, LL is max length. With N=1000,M=1000N=1000, M=1000, this is roughly 10610^6 checks per word, leading to potential timeout risks in Python given the large input size.
  • Optimization: We need a data structure that allows us to check “does a prefix exist?” efficiently. A Trie (Prefix Tree) is ideal here. By inserting all roots into a Trie and marking nodes where a root ends, we can traverse the sentence word character by character. The moment we hit a marked node during traversal, we have found the shortest matching root because we are traversing from the beginning of the word.

Approach

  1. Build the Trie: Iterate through every root in the dictionary. For each character in the root, create nodes if they don’t exist. Mark the final node of each root with a special flag (e.g., is_end = True) to indicate a valid root ends there.
  2. Process Sentence: Split the sentence into individual words.
  3. Lookup & Replace: For each word:
    • Traverse the Trie character by character.
    • If we encounter a node marked as is_end, we have found the shortest root for this word. We replace the current word with the prefix corresponding to that depth and stop traversing for this word.
    • If we finish traversing the word without hitting an is_end node, or if a character in the word doesn’t exist in the Trie path, keep the original word.
  4. Reconstruct: Join the processed words back into a single string with spaces.

Complexity Analysis

  • Time Complexity: O(D⋅L+N⋅L)O(D \cdot L + N \cdot L), where DD is the total number of characters in the dictionary (to build the Trie), NN is the number of words in the sentence, and LL is the maximum length of a word. Building the Trie takes linear time relative to dictionary size. Processing each word takes time proportional to its length (bounded by root length).
  • Space Complexity: O(D⋅L)O(D \cdot L) to store the Trie nodes. In the worst case, every character in the dictionary creates a unique node.

Solution

from typing import List

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        # Build the Trie from the dictionary
        trie = {}
        for root in dictionary:
            node = trie
            for char in root:
                if char not in node:
                    node[char] = {}
                node = node[char]
            # Mark the end of a valid root
            node['#'] = True
            
        words = sentence.split()
        result_words = []
        
        for word in words:
            curr = trie
            replaced = False
            # Traverse the Trie with the current word
            for i, char in enumerate(word):
                if char not in curr:
                    break
                curr = curr[char]
                # If we hit a marked node, this is the shortest root match
                if '#' in curr:
                    result_words.append(word[:i+1])
                    replaced = True
                    break
            
            # If no root was found, keep the original word
            if not replaced:
                result_words.append(word)
                
        return ' '.join(result_words)

Edge Cases Handled

  • No Match: If a word in the sentence shares no prefix with any root, the loop finishes without replaced being set, and the original word is appended.
  • Multiple Matches: The Trie traversal stops at the first marked node (#). Since we traverse from index 0, the first match encountered corresponds to the shortest length root (e.g., “a” before “aa”).
  • Partial Match: If a word starts with a prefix that exists in the dictionary but continues further (e.g., root “cat”, word “cattle”), the traversal stops at ‘t’ because # is marked, replacing “cattle” with “cat”.
  • Empty Dictionary/Word: Constraints guarantee non-empty inputs, but the logic naturally handles empty lists by returning the original sentence.