LeetCode 648: Replace Words

A trie-based solution for replacing each derivative word with the shortest matching root.

leetcodetriestringhash-table

Problem Restatement

We are given a dictionary of root words and a sentence.

A root can form a longer derivative word.

For example:

root = "cat"
derivative = "cattle"

Since "cattle" starts with "cat", we can replace "cattle" with "cat".

For every word in the sentence, if it starts with one or more roots from the dictionary, replace it with the shortest matching root.

If no root matches, keep the word unchanged.

Input and Output

Item Meaning
Input dictionary, a list of root words, and sentence, a string
Output Sentence after replacing derivatives with roots
Rule If multiple roots match, use the shortest root
Sentence format Words are separated by one space

Example function shape:

def replaceWords(dictionary: list[str], sentence: str) -> str:
    ...

Examples

Example 1:

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

Replacement:

Word Matching Root Result
the none the
cattle cat cat
was none was
rattled rat rat
by none by
battery bat bat

Output:

"the cat was rat by the bat"

Example 2:

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

Output:

"a a b c"

Each word starts with one of the single-character roots.

First Thought: Check Every Root

For each word in the sentence, we could check every root in the dictionary.

If the word starts with that root, keep the shortest one.

class Solution:
    def replaceWords(self, dictionary: list[str], sentence: str) -> str:
        roots = set(dictionary)
        answer = []

        for word in sentence.split():
            replacement = word

            for i in range(1, len(word) + 1):
                prefix = word[:i]
                if prefix in roots:
                    replacement = prefix
                    break

            answer.append(replacement)

        return " ".join(answer)

This already works well because we check prefixes from shortest to longest.

But a trie gives a more structured prefix-search solution.

Key Insight

We need to answer this question many times:

What is the shortest dictionary root that is a prefix of this word?

A trie is designed for prefix lookup.

We insert every root into the trie.

Then for each sentence word, we walk through the trie character by character.

The first time we reach a node marked as a complete root, we return that root immediately.

This automatically gives the shortest matching root because we scan from left to right.

Trie Structure

Each trie node stores:

Field Meaning
children Map from character to next trie node
word The complete root if this node ends a root

For example, with roots:

["cat", "bat", "rat"]

the trie has paths for:

c -> a -> t
b -> a -> t
r -> a -> t

The node for "cat" is marked as a complete root.

Algorithm

  1. Build a trie from all roots in dictionary.
  2. Split sentence into words.
  3. For each word:
    1. Start at the trie root.
    2. Scan the word character by character.
    3. If the current trie node ends a root, return that root.
    4. If the next character is missing from the trie, return the original word.
    5. Otherwise, continue.
  4. Join the replaced words with spaces.

Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

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

        for word in dictionary:
            node = root

            for ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]

            node.word = word

        def replace(word: str) -> str:
            node = root

            for ch in word:
                if node.word is not None:
                    return node.word

                if ch not in node.children:
                    return word

                node = node.children[ch]

            if node.word is not None:
                return node.word

            return word

        words = sentence.split()
        replaced = [replace(word) for word in words]

        return " ".join(replaced)

Code Explanation

First, we build the trie:

root = TrieNode()

For every dictionary root, we create a path through the trie.

for ch in word:
    if ch not in node.children:
        node.children[ch] = TrieNode()
    node = node.children[ch]

At the end of the root, we store the complete word:

node.word = word

This marks the node as a root endpoint.

The replacement function walks through one sentence word:

def replace(word: str) -> str:

Before going deeper, it checks whether the current node already ends a root:

if node.word is not None:
    return node.word

This is what guarantees the shortest root.

If the path breaks:

if ch not in node.children:
    return word

then no root can match this word, so we keep the original word.

At the end, we replace each word and join the result:

return " ".join(replaced)

Correctness

Every root in dictionary is inserted into the trie, and the node at the end of that root stores the root itself.

For any word in the sentence, the algorithm scans its characters from left to right. At each step, the trie path corresponds exactly to the prefix of the word scanned so far.

If the algorithm reaches a node with word set, then that prefix is a dictionary root. Since the scan proceeds from shortest prefix to longer prefix, this is the shortest matching root, so returning it is correct.

If the trie path breaks before reaching a root endpoint, then no dictionary root can match the word along this prefix path. Therefore, the word has no matching root and should remain unchanged.

If the scan finishes and the final node is a root endpoint, the whole word itself is a root and should be returned.

Thus every word is replaced exactly according to the problem rule, and joining the words gives the correct sentence.

Complexity

Let:

D = total number of characters in dictionary
S = total number of characters in sentence
Metric Value Why
Time O(D + S) Build the trie once, then scan sentence words
Space O(D) Trie stores dictionary roots

Each sentence word is scanned only until its shortest root is found or the trie path breaks.

Alternative Solution: Prefix Set

Because we only need the shortest prefix, a set of roots is also enough.

class Solution:
    def replaceWords(self, dictionary: list[str], sentence: str) -> str:
        roots = set(dictionary)
        result = []

        for word in sentence.split():
            replacement = word

            for length in range(1, len(word) + 1):
                prefix = word[:length]

                if prefix in roots:
                    replacement = prefix
                    break

            result.append(replacement)

        return " ".join(result)

This is simpler and often fast enough.

Metric Value Why
Time O(S * L) in slicing cost Prefix strings are created while checking
Space O(D) Stores roots in a set

The trie avoids repeatedly constructing many prefixes.

Testing

def run_tests():
    s = Solution()

    assert s.replaceWords(
        ["cat", "bat", "rat"],
        "the cattle was rattled by the battery",
    ) == "the cat was rat by the bat"

    assert s.replaceWords(
        ["a", "b", "c"],
        "aadsfasf absbs bbab cadsfafs",
    ) == "a a b c"

    assert s.replaceWords(
        ["c", "cat"],
        "cattle cat category",
    ) == "c c c"

    assert s.replaceWords(
        ["blue", "green"],
        "red yellow black",
    ) == "red yellow black"

    assert s.replaceWords(
        ["app", "apple"],
        "applepie apple app",
    ) == "app app app"

    print("all tests passed")

run_tests()

Test meaning:

Test Why
Official-style sample Normal replacements
Single-character roots Short roots replace many words
Multiple matching roots Shortest root wins
No matches Words remain unchanged
Word equals root Exact root is returned