648. Replace Words — DSA Atlas

648

MediumTrie and Advanced String SearchTrie prefix lookupShortest-prefix root replacement

Replace Words

Given a dictionary of root words and a sentence, replace every word in the sentence with the shortest root in the dictionary that is a prefix of it. If no root is a prefix, keep the word unchanged. Return the resulting sentence.

Open official problem prompt ↗

In plain English

Rewrite each word in a sentence to the shortest dictionary root that begins it, leaving unmatched words alone.

Picture it like this

Like autocorrect shrinking 'cattle' to its known stem 'cat' the instant it recognizes a complete root, not waiting to read the rest of the word.

Example

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Why: "cattle" -> "cat", "rattled" -> "rat", "battery" -> "bat"; words with no root prefix stay the same.

Constraints

1 <= dictionary.length <= 10001 <= dictionary[i].length <= 100dictionary[i] consists of only lowercase letters1 <= sentence.length <= 10^6words in sentence are separated by single spaces1 <= word length <= 1000

Pattern lesson

See the pattern, then code

Shortest-prefix root replacement

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. Store all roots in a trie; walking a word letter by letter, the first node marked as a root end is necessarily the shortest root prefix, so stop immediately.

New words, made simpleKnow these before the algorithm

Root: A dictionary word that may be a prefix of longer words (the successor).
Successor: The longer word being replaced by its root.
Terminal node: A trie node that marks the end of a complete root.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Prefix set of all substrings

Quadratic per word and slower to find the shortest root.

For each word, test each prefix against a hash set of roots.

Time O(sum of word_len^2)Space O(D)

Best choiceTrie walk

Finds the shortest root in a single left-to-right pass.

One trie of roots; walk each word and stop at the first terminal.

Time O(D + S)Space O(D)

The rule we keep true

Invariant

The first terminal node encountered while descending a word is the shortest root that is a prefix of that word.

Why this is correct

Reasoning

The trie is traversed strictly by increasing prefix length, so the earliest terminal marker corresponds to the shortest complete root; stopping there guarantees minimality.

The algorithm in three movesSay these aloud before coding

1Insert every root into a trie, marking terminal nodes

trie: c-a-t($), b-a-t($), r-a-t($)

2For each word in the sentence, walk down the trie character by character

word 'cattle': c->a->t hits $

3Stop and return the root the moment a terminal marker is hit

emit 'cat'

4If a character is missing from the trie, keep the original word

5Join the transformed words with spaces

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

cattle3

1 · Read['cat','bat','rat']

2 · AskStore each root?

3 · Update statethree 3-letter paths with $

4 · Resulttrie ready

Key takeaway

Walking 'cattle' hits the root end at 'cat', so 'cat' replaces it.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-8Build root trie
Each root is a path ending in a '$' marker holding the root string.
2
Lines 10-19Shortest-root lookup
Descend per character; return at the first '$', or return the original word if a character is absent.
3
Lines 21Reassemble
Split on spaces, map each word, and join back into a sentence.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A word with no matching root stays unchanged
A word that exactly equals a root
One root that is a prefix of another (shortest wins)
Single-word sentence

Common beginner mistakes

Returning the longest instead of the shortest root by not stopping at the first terminal
Forgetting to keep the original word when no root matches
Splitting on multiple spaces incorrectly (input uses single spaces)
Rebuilding the root by hand instead of storing it at the terminal

Check your understanding

If two roots 'cat' and 'ca' both prefix a word, which is chosen and why?

PyPython 3 · solution.py

Optimal

1class Solution:2    def replaceWords(self, dictionary: List[str], sentence: str) -> str:3        trie = {}4        for root in dictionary:5            node = trie6            for ch in root:7                node = node.setdefault(ch, {})8            node['$'] = root910        def shortest_root(word):11            node = trie12            for ch in word:13                if ch not in node:14                    return word15                node = node[ch]16                if '$' in node:17                    return node['$']18            return word1920        return ' '.join(shortest_root(w) for w in sentence.split())

Time complexityO(D + S) where D is total root chars and S is sentence lengthOptimized

Space complexityO(D) for the trieExplained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftRoblox

Replace Words

Replace Words

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search