Replace Words

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

Why this is worth learning

The shortest matching root is the first terminal encountered while walking a sentence word. Unlike longest-prefix routing, continuing past that terminal would solve the wrong problem.

Before coding: one-minute experiment

With roots ["cat","c","cattle"], what replaces "cattle"? Does dictionary insertion order affect the result?

Function signature

func ReplaceWords(dictionary []string, sentence string) string

Inputs / outputs

• dictionary: list of lowercase root words.
• sentence: lowercase words separated by single spaces.
• Return: sentence after root replacement.

Example

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

Constraints

• Dictionary and sentence contain lowercase English words.
• Preserve word order and spaces between words.

Core idea (near-solution)

A direct solution checks every dictionary root against each sentence word and keeps the shortest matching prefix. A trie shares those repeated prefix comparisons. As a word is consumed, reaching the first terminal proves both membership and minimality: every shorter prefix was visited and was not terminal. Stop immediately there. If the path breaks before any terminal, no longer root can match and the original word survives. This is shortest-prefix replacement, not arbitrary substring matching or longest-prefix replacement.

Invariant: after scanning i characters of a word, the current trie node represents that prefix, and no shorter terminal prefix has been missed.

Algorithm (step-by-step)

1. Insert every root into a trie.
2. Split the sentence into words.
3. For each word, traverse the trie by its characters.
4. If a terminal node is reached, replace with the prefix scanned so far.
5. If a character path is missing, keep the original word.
6. Join the transformed words with spaces.

Correctness sketch

After i bytes, the trie walk has checked every shorter prefix of the word. If the current node is terminal, that prefix is a dictionary root and no earlier prefix was terminal, so it is the shortest possible replacement. If a required child is absent, no dictionary root can extend the consumed prefix, and no earlier root was found; the original word must remain unchanged. Applying this independent rule to each word preserves word order. Under the single-space sentence contract, Fields followed by Join preserves the specified separators exactly.

Trace (hand walkthrough)

word = battery
b -> ba -> bat is terminal
shortest root found, return bat

Pitfalls to avoid

• Choosing a longer root when a shorter one exists.
• Splitting or joining in a way that changes word order.
• Forgetting that words without roots remain unchanged.

Debugging lens

Do not overwrite the answer with a later, longer terminal. Test an unchanged word and two roots nested within each other. The current tokenizer is not a whitespace-preserving general text editor.

Complexity

Expected/array-transition time O(D + S), with D total dictionary characters and S sentence bytes. Trie space O(D); token slice, joined output, and replacement bookkeeping add O(S) space. The returned sentence itself is O(S).

Implementation notes (Go)

• strings.Fields and strings.Join match the usual single-space sentence constraints.
• A helper that returns the replacement for one word keeps the main function simple.

Contract precision

Inputs use nonempty lowercase English roots and lowercase words separated by single spaces. Under that domain, spacing is preserved. The existing strings.Fields implementation collapses repeated/leading/trailing whitespace outside that domain; no broader whitespace-preservation promise is introduced.

Reconstruction checkpoint

Roots are ["be","bee","sun"], sentence is "bees sunset bedroom". Derive the output without relying on insertion order. If the task instead demanded longest roots, which stopping rule would change?

Return to Trie · Module quiz