Problem Description

This problem asks you to replace words in a sentence with their root forms using a given dictionary of roots.

Key Concepts:

• A root is a base word (like "help")
• A derivative is a longer word that starts with a root (like "helpful" which starts with "help")
• You're given a dictionary containing multiple roots
• You're given a sentence with words separated by spaces

Task: Replace each word in the sentence that is a derivative with its corresponding root from the dictionary.

Rules for Replacement:

1. If a word starts with a root from the dictionary, replace the entire word with that root
2. If a word can be replaced by multiple roots (meaning it starts with multiple different roots from the dictionary), choose the shortest root
3. If a word doesn't start with any root from the dictionary, keep it unchanged

Example:

• Dictionary: ["help", "hel"]
• Sentence: "helpful helping hello"
• Result: "hel hel hello"
  • "helpful" starts with both "help" and "hel", but "hel" is shorter, so we use "hel"
  • "helping" starts with both "help" and "hel", but "hel" is shorter, so we use "hel"
  • "hello" starts with "hel", so it becomes "hel"

The solution uses a Trie data structure to efficiently store all roots and find the shortest matching root for each word. The Trie allows checking prefixes character by character and returning immediately when the first (shortest) root is found.

Intuition

The naive approach would be to check every word in the sentence against every root in the dictionary to see if the word starts with that root. However, this would be inefficient, especially when we have many roots or long words.

The key insight is that we're looking for prefixes - we want to find if any root is a prefix of the current word. This naturally leads us to think about a Trie (prefix tree), which is specifically designed for efficient prefix matching.

Why is a Trie perfect here?

1. Efficient prefix search: As we traverse each character of a word, we can simultaneously check if we've formed a complete root at any point. The moment we find a root, we can stop - this automatically gives us the shortest root since we're checking character by character from the beginning.

2. Early termination: If we're checking the word "helpful" and our dictionary has both "hel" and "help", we'll encounter "hel" first (after 3 characters) and can immediately return it without checking further. This guarantees we always get the shortest matching root.

3. No redundant comparisons: Without a Trie, checking if "helpful" starts with "help" requires comparing 4 characters. If we have 100 roots, we might need to do this comparison 100 times for each word. With a Trie, we traverse the word only once, following the path down the tree.

The algorithm becomes straightforward:

• Build a Trie from all dictionary roots
• For each word in the sentence, traverse it character by character in the Trie
• As soon as we hit a node that marks the end of a root (ref != -1), we've found our shortest replacement
• If we can't continue in the Trie (no matching child), the word has no root prefix

The ref field in each Trie node stores the index of the root in the dictionary, allowing us to quickly retrieve the replacement word when we find a match.

Learn more about Trie patterns.

Solution Approach

The solution uses a Trie data structure to efficiently find and replace words with their shortest root forms.

Trie Implementation

The [Trie](/problems/trie_intro) class has the following components:

1. Node Structure:

   • children: An array of 26 elements (for lowercase letters a-z), where each element can be either None or another Trie node
   • ref: An integer that stores the index of the root word in the dictionary (-1 if this node doesn't represent a complete root)

2. Insert Method (insert(w, i)):

   def insert(self, w: str, i: int):
       node = self
       for c in w:
           idx = ord(c) - ord("a")  # Convert character to index (0-25)
           if node.children[idx] is None:
               node.children[idx] = [Trie](/problems/trie_intro)()  # Create new node if path doesn't exist
           node = node.children[idx]
       node.ref = i  # Mark the end of this root with its dictionary index

   • Traverses each character of the root word
   • Creates new nodes as needed along the path
   • Marks the final node with the root's index in the dictionary

3. Search Method (search(w)):

   def search(self, w: str) -> int:
       node = self
       for c in w:
           idx = ord(c) - ord("a")
           if node.children[idx] is None:
               return -1  # No matching prefix found
           node = node.children[idx]
           if node.ref != -1:
               return node.ref  # Found a root! Return its index immediately
       return -1  # Traversed entire word without finding a root

   • Traverses the word character by character
   • Returns immediately when finding the first (shortest) root
   • Returns -1 if no root prefix exists

Main Algorithm

The replaceWords method follows these steps:

1. Build the Trie:

   trie = Trie()
   for i, w in enumerate(dictionary):
       trie.insert(w, i)

   • Insert all roots from the dictionary into the Trie
   • Each root is stored with its index for quick retrieval

2. Process the sentence:

   ans = []
   for w in sentence.split():
       idx = [trie](/problems/trie_intro).search(w)
       ans.append(dictionary[idx] if idx != -1 else w)

   • Split the sentence into individual words
   • For each word, search for a root prefix in the Trie
   • If a root is found (idx != -1), replace with dictionary[idx]
   • Otherwise, keep the original word

3. Return the result:

   return " ".join(ans)

   • Join all processed words back into a sentence

Time and Space Complexity

• Time Complexity:

  • Building Trie: O(N × L) where N is the number of roots and L is the average length of roots
  • Processing sentence: O(M × W) where M is the number of words and W is the average word length
  • Overall: O(N × L + M × W)

• Space Complexity: O(N × L) for storing the Trie structure

The beauty of this approach is that the Trie automatically handles the "shortest root" requirement - by returning as soon as we find a complete root during traversal, we guarantee we're always using the shortest possible replacement.

Example Walkthrough

Let's walk through a concrete example to understand how the Trie-based solution works.

Given:

• Dictionary: ["cat", "bat", "rat"]
• Sentence: "the cattle was rattled by the battery"

Step 1: Build the Trie

We insert each root into the Trie:

Insert "cat":
    root
     |
     c (ref=-1)
     |
     a (ref=-1)
     |
     t (ref=0) ← marks end of "cat" with index 0

Insert "bat":
    root
    / \
   c   b (ref=-1)
   |   |
   a   a (ref=-1)
   |   |
   t   t (ref=1) ← marks end of "bat" with index 1
  (ref=0)

Insert "rat":
    root
   /|\
  c b r (ref=-1)
  | | |
  a a a (ref=-1)
  | | |
  t t t (ref=2) ← marks end of "rat" with index 2

Step 2: Process Each Word

Now we search for each word in the sentence:

1. "the":

   • Try to traverse: t → h → e
   • 't' doesn't exist as a child of root
   • Return -1 (no root found)
   • Keep original: "the"

2. "cattle":

   • Traverse: c → a → t
   • At 't', we find ref=0 (this is the end of root "cat")
   • Return index 0 immediately (don't need to check 't', 'l', 'e')
   • Replace with: dictionary[0] = "cat"

3. "was":

   • Try to traverse: w → a → s
   • 'w' doesn't exist as a child of root
   • Return -1 (no root found)
   • Keep original: "was"

4. "rattled":

   • Traverse: r → a → t
   • At 't', we find ref=2 (this is the end of root "rat")
   • Return index 2 immediately (don't need to check 't', 'l', 'e', 'd')
   • Replace with: dictionary[2] = "rat"

5. "by":

   • Try to traverse: b → y
   • After 'b', we try to find 'y' but it doesn't exist
   • Return -1 (no root found)
   • Keep original: "by"

6. "the":

   • Same as step 1
   • Keep original: "the"

7. "battery":

   • Traverse: b → a → t
   • At 't', we find ref=1 (this is the end of root "bat")
   • Return index 1 immediately (don't need to check 't', 'e', 'r', 'y')
   • Replace with: dictionary[1] = "bat"

Step 3: Build Result

Join the processed words: ["the", "cat", "was", "rat", "by", "the", "bat"]

Final Output: "the cat was rat by the bat"

The key insight is that by returning immediately when we find a complete root (ref != -1), we automatically get the shortest possible root. For example, if our dictionary also contained "catt", we would still return "cat" for "cattle" because we encounter "cat" first during our character-by-character traversal.

Solution Implementation

Time and Space Complexity

Time Complexity: O(D × L + S × M)

Where:

• D = number of words in dictionary
• L = average length of dictionary words
• S = number of words in sentence
• M = average length of sentence words

Breaking down the operations:

1. Building the Trie: For each word in dictionary, we insert it character by character. This takes O(D × L) time.
2. Processing the sentence: For each word in the sentence, we search in the Trie up to M characters (in worst case). This takes O(S × M) time.
3. Joining the result: O(S) time to join the words, which is dominated by the above operations.

Space Complexity: O(D × L × 26 + S)

Where the components are:

1. Trie storage: In the worst case, if all dictionary words have completely different prefixes, we need O(D × L) nodes. Each node contains an array of 26 pointers, giving us O(D × L × 26) space.
2. Result list: O(S) space to store the processed words.
3. The split operation creates a list of S words, but this is temporary and dominated by the Trie space.

Note: The space complexity can be more precisely stated as O(ALPHABET_SIZE × N + S) where N is the total number of nodes in the Trie and ALPHABET_SIZE = 26.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling the "Shortest Root" Requirement Correctly

A common mistake is implementing a solution that finds any matching root rather than the shortest one. For example, using a simple string matching approach:

Incorrect Approach:

def replaceWords(dictionary, sentence):
    words = sentence.split()
    for i, word in enumerate(words):
        for root in dictionary:  # This doesn't guarantee shortest root!
            if word.startswith(root):
                words[i] = root
                break
    return " ".join(words)

Problem: If dictionary = ["help", "hel"] and word = "helpful", this might replace with "help" instead of "hel" depending on dictionary order.

Solution: The Trie approach naturally solves this by returning immediately upon finding the first complete root during character-by-character traversal, which is guaranteed to be the shortest.

2. Inefficient Dictionary Lookup Using Nested Loops

Inefficient Approach:

def replaceWords(dictionary, sentence):
    # Sort to get shortest roots first
    dictionary.sort(key=len)
    result = []
    for word in sentence.split():
        replaced = False
        for root in dictionary:
            if word.startswith(root):
                result.append(root)
                replaced = True
                break
        if not replaced:
            result.append(word)
    return " ".join(result)

Problem: This has O(M × N) complexity where M is the number of words and N is the size of dictionary. For large dictionaries, this becomes very slow.

Solution: The Trie reduces the search to O(W) where W is the word length, independent of dictionary size.

3. Memory Issues with Character Index Calculation

Common Bug:

# Forgetting to handle only lowercase letters
char_index = ord(char) - ord('a')  # Assumes lowercase only!

Problem: If the input contains uppercase letters or special characters, this will cause index out of bounds errors or incorrect behavior.

Solution: Either validate input or normalize it:

def search(self, word: str) -> int:
    node = self
    for char in word:
        if not char.islower():
            return -1  # Handle non-lowercase characters
        char_index = ord(char) - ord('a')
        if node.children[char_index] is None:
            return -1
        node = node.children[char_index]
        if node.ref != -1:
            return node.ref
    return -1

4. Not Preserving Word Spacing

Incorrect Handling:

# Using wrong split method
words = sentence.split(' ')  # This doesn't handle multiple spaces correctly

Problem: If the sentence has multiple consecutive spaces, split(' ') will create empty strings in the result.

Solution: Use split() without arguments, which handles any whitespace correctly and filters out empty strings. Then use single space in join():

words = sentence.split()  # Handles any whitespace
return " ".join(result)   # Ensures single space between words

5. Trie Node Reference Overwriting

Potential Bug:

def insert(self, word: str, index: int):
    # ... traversal code ...
    node.ref = index  # What if this node already has a ref?

Problem: If multiple roots share the same prefix (e.g., "he" and "help"), the shorter one might get overwritten.

Solution: Only update if not already set, or ensure dictionary is processed in order of increasing length:

def insert(self, word: str, index: int):
    node = self
    for char in word:
        char_index = ord(char) - ord('a')
        if node.children[char_index] is None:
            node.children[char_index] = Trie()
        node = node.children[char_index]
    # Only set if not already a word (preserves shorter roots)
    if node.ref == -1:
        node.ref = index

Or sort dictionary by length before inserting:

# In replaceWords method
sorted_dict = sorted(enumerate(dictionary), key=lambda x: len(x[1]))
for original_index, word in sorted_dict:
    trie.insert(word, original_index)