LeetCode 648: Replace Words

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

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:

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:

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

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.

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: