LeetCode 648 - Replace Words

The problem asks us to replace words in a sentence using a set of predefined root words. A root is a shorter word that can serve as a prefix for a longer derivative word.

leetcodemediumarrayhash-tablestringtrie

LeetCode Problem 648

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Trie

Solution

Problem Understanding

The problem asks us to replace words in a sentence using a set of predefined root words. A root is a shorter word that can serve as a prefix for a longer derivative word. Whenever a word in the sentence starts with one of the roots from the dictionary, we replace that word with the matching root.

There is one important rule: if multiple roots can match a word, we must always choose the shortest root. For example, if the dictionary contains both "cat" and "cattle", and the sentence contains "cattleman", the correct replacement is "cat" because it is the shortest valid prefix.

The input consists of two parts:

  • dictionary, a list of root words.
  • sentence, a string containing space-separated words.

The expected output is a modified sentence where every derivative word is replaced by its shortest matching root, while words that do not match any root remain unchanged.

For example:

dictionary = ["cat","bat","rat"]
sentence = "the cattle was rattled by the battery"

The word "cattle" starts with "cat", so it becomes "cat". "rattled" starts with "rat", so it becomes "rat". "battery" starts with "bat", so it becomes "bat".

The constraints are important because they influence the choice of algorithm. The dictionary can contain up to 1000 roots, each up to length 100. A sentence can be as long as 10^6 characters, and each word may also be quite large. A naive solution that repeatedly scans every root for every word could become inefficient when both the sentence and dictionary are large.

Several edge cases are worth identifying upfront. A word may not match any root at all, in which case it should remain unchanged. Multiple roots may match the same word, and we must choose the shortest one. Some roots may themselves be prefixes of other roots, such as "a" and "ab", which makes shortest-prefix selection especially important. The problem guarantees that the input contains only lowercase letters and spaces, with exactly one space between words, which simplifies parsing.

Approaches

Brute Force Approach

A straightforward solution is to check every word in the sentence against every root in the dictionary.

For each word, we iterate through all dictionary entries and determine whether the root is a prefix of the current word. If multiple roots match, we keep track of the shortest one. If no root matches, we leave the word unchanged.

This approach is correct because it explicitly checks all possible roots and chooses the shortest valid prefix. However, it becomes inefficient when the dictionary is large. For every word, we potentially scan all roots, and prefix checking itself may take additional time proportional to the root length.

If:

  • n = number of words
  • d = number of dictionary roots
  • k = average root length

Then the time complexity becomes approximately O(n × d × k), which may be unnecessarily expensive.

Key Insight for an Optimal Solution

The main observation is that we are repeatedly performing prefix lookups. This is exactly the kind of problem a Trie (Prefix Tree) is designed to solve efficiently.

A Trie stores words character by character. Instead of checking every root independently, we insert all dictionary roots into a Trie. Then, for each sentence word, we traverse the Trie character by character.

The moment we encounter a node marked as the end of a root, we stop immediately because the first root we encounter is automatically the shortest prefix. If traversal fails because a character does not exist in the Trie, then no replacement exists.

This avoids repeatedly scanning the entire dictionary and makes prefix matching much faster.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × d × k) O(d × k) Check every root against every word
Optimal (Trie) O(D + S) O(D) Efficient prefix lookup using a Trie

Here:

  • D is the total number of characters across all dictionary words.
  • S is the total number of characters across all sentence words.

Algorithm Walkthrough

Optimal Algorithm Using a Trie

  1. Build a Trie from the dictionary roots

Create a Trie where each node stores child characters and a marker indicating whether a root ends there. Insert every root into the Trie one character at a time.

This preprocessing step allows us to perform prefix lookups efficiently instead of repeatedly scanning the dictionary. 2. Split the sentence into words

Since the sentence contains words separated by spaces, we split it into an array of words.

This allows us to process each word independently. 3. Search for the shortest matching root

For each word:

  • Start traversing the Trie from the root node.
  • Move character by character through the word.
  • If a character does not exist in the Trie, stop because no root matches.
  • If we encounter a Trie node marked as the end of a root, immediately return the substring up to this position.

We stop at the first valid root because Trie traversal naturally finds shorter prefixes before longer ones. 4. Replace the word if needed

If a matching root is found, append the root to the result list. Otherwise, append the original word unchanged. 5. Reconstruct the sentence

Join all processed words back together using spaces.

Why it works

The key invariant is that Trie traversal follows prefixes in increasing order of length. As soon as we encounter a node marked as a complete root, we know it is the shortest possible valid root because any longer root would extend beyond this point. Therefore, replacing a word at the first valid root always satisfies the problem requirement.

Python Solution

from typing import List

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

class Solution:
    def replaceWords(self, dictionary: List[str], sentence: str) -> str:
        root = TrieNode()

        # Build Trie
        for word in dictionary:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.is_end = True

        def find_root(word: str) -> str:
            node = root
            prefix = []

            for char in word:
                if char not in node.children:
                    return word

                node = node.children[char]
                prefix.append(char)

                if node.is_end:
                    return "".join(prefix)

            return word

        words = sentence.split()
        replaced_words = [find_root(word) for word in words]

        return " ".join(replaced_words)

The implementation begins by defining a TrieNode class. Each node contains a dictionary of child nodes and a boolean flag indicating whether a root word ends at that node.

The Trie is constructed by iterating through every dictionary root and inserting characters one by one. If a character path does not exist, a new node is created. Once the entire word is inserted, the ending node is marked as a valid root.

The helper function find_root performs prefix searching. It walks through the Trie character by character while simultaneously building the prefix. If traversal fails, the original word is returned because no root exists. If an ending node is encountered, the shortest valid root is returned immediately.

Finally, the sentence is split into words, transformed using the helper function, and reconstructed with spaces.

Go Solution

package main

import "strings"

type TrieNode struct {
	children map[byte]*TrieNode
	isEnd    bool
}

func newTrieNode() *TrieNode {
	return &TrieNode{
		children: make(map[byte]*TrieNode),
	}
}

func replaceWords(dictionary []string, sentence string) string {
	root := newTrieNode()

	// Build Trie
	for _, word := range dictionary {
		node := root

		for i := 0; i < len(word); i++ {
			char := word[i]

			if _, exists := node.children[char]; !exists {
				node.children[char] = newTrieNode()
			}

			node = node.children[char]
		}

		node.isEnd = true
	}

	findRoot := func(word string) string {
		node := root

		for i := 0; i < len(word); i++ {
			char := word[i]

			nextNode, exists := node.children[char]
			if !exists {
				return word
			}

			node = nextNode

			if node.isEnd {
				return word[:i+1]
			}
		}

		return word
	}

	words := strings.Split(sentence, " ")

	for i := 0; i < len(words); i++ {
		words[i] = findRoot(words[i])
	}

	return strings.Join(words, " ")
}

The Go implementation follows the same overall structure as the Python version but uses a map[byte]*TrieNode to represent child edges in the Trie. Since the problem guarantees lowercase English letters, byte indexing is sufficient and efficient.

Instead of a nested helper function returning lists of characters, Go simply slices the original string with word[:i+1] once a valid root is found. The sentence is split using strings.Split, and the final sentence is rebuilt with strings.Join.

No special handling for nil is required because the constraints guarantee non-empty input, though the implementation would still behave correctly for empty slices.

Worked Examples

Example 1

Input

dictionary = ["cat","bat","rat"]
sentence = "the cattle was rattled by the battery"

Step 1: Build the Trie

The Trie contains these root paths:

cat
bat
rat

Step 2: Process Words

Word Trie Traversal Match Found Output
the t not found No the
cattle c → a → t cat cat
was w not found No was
rattled r → a → t rat rat
by b exists, next fails No root end by
the t not found No the
battery b → a → t bat bat

Final result:

"the cat was rat by the bat"

Example 2

Input

dictionary = ["a","b","c"]
sentence = "aadsfasf absbs bbab cadsfafs"

Step 1: Build Trie

The Trie contains:

a
b
c

Step 2: Process Words

Word Match Output
aadsfasf a a
absbs a a
bbab b b
cadsfafs c c

Final result:

"a a b c"

Complexity Analysis

Measure Complexity Explanation
Time O(D + S) Building the Trie takes O(D), processing the sentence takes O(S)
Space O(D) The Trie stores all dictionary characters

The preprocessing cost is proportional to the total number of characters in the dictionary. During lookup, each character in the sentence is visited at most once while traversing the Trie. Since traversal stops early whenever a root is found or a mismatch occurs, the algorithm remains efficient even for long words.

Test Cases

solution = Solution()

# Example 1
assert solution.replaceWords(
    ["cat", "bat", "rat"],
    "the cattle was rattled by the battery"
) == "the cat was rat by the bat"  # basic replacement case

# Example 2
assert solution.replaceWords(
    ["a", "b", "c"],
    "aadsfasf absbs bbab cadsfafs"
) == "a a b c"  # single-character roots

# No matching roots
assert solution.replaceWords(
    ["cat", "dog"],
    "bird fish mouse"
) == "bird fish mouse"  # unchanged sentence

# Multiple matching roots, shortest should win
assert solution.replaceWords(
    ["a", "aa", "aaa"],
    "aaaaaa"
) == "a"  # shortest root priority

# Root equals full word
assert solution.replaceWords(
    ["cat"],
    "cat cattle"
) == "cat cat"  # exact word match

# Single word sentence
assert solution.replaceWords(
    ["ab"],
    "abcdef"
) == "ab"  # minimal input structure

# Long root chain
assert solution.replaceWords(
    ["a", "ab", "abc", "abcd"],
    "abcdefg"
) == "a"  # earliest valid prefix

# No replacement after partial prefix
assert solution.replaceWords(
    ["abc"],
    "abx"
) == "abx"  # prefix mismatch

# Large repeated sentence
assert solution.replaceWords(
    ["x"],
    "xylophone xyz xray"
) == "x x x"  # repeated replacements
Test Why
Example 1 Validates standard replacement behavior
Example 2 Tests single-character roots
No matching roots Ensures unchanged words remain intact
Multiple matching roots Confirms shortest root selection
Root equals full word Verifies exact matches work
Single word sentence Tests minimal sentence structure
Long root chain Ensures earliest root is selected
Partial prefix mismatch Prevents false positives
Large repeated sentence Validates repeated Trie usage

Edge Cases

Multiple Roots Match the Same Word

A word may match several roots simultaneously. For example, if the dictionary contains ["a", "ab", "abc"] and the word is "abcdef", all three roots are technically valid prefixes.

This is a common source of bugs because an implementation might accidentally return the longest match. The Trie-based solution avoids this naturally by stopping at the first ending node, which guarantees the shortest root.

No Root Matches

Some words may not begin with any dictionary root. For example:

dictionary = ["cat"]
sentence = "dog"

A naive implementation might incorrectly return an empty string or partially matched prefix. In this implementation, Trie traversal immediately fails when the first character is missing, and the original word is returned unchanged.

Root Is the Entire Word

Sometimes a word already equals a root exactly, such as:

dictionary = ["cat"]
sentence = "cat cattle"

The implementation correctly handles this because Trie traversal marks the final node as is_end. Once reached, the word is replaced with "cat", even if it already matches perfectly. This guarantees consistent behavior for both exact matches and derivatives.