Replace Words

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

Function signature

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

Inputs / outputs

• dictionary: list of root words.
• sentence: space-separated words.
• Return: sentence with replacements applied.

Example

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

Constraints

• 1 <= total characters <= 100_000

Core idea (near-solution)

Build a trie of roots. For each word, walk the trie until you either hit an isWord node (shortest root) or a missing edge.

Invariant: the first isWord encountered along the trie path is the shortest valid replacement.

Algorithm (step-by-step)

1. Insert all dictionary roots into a trie.
2. For each word in the sentence:
   • Walk the trie character by character.
   • If an isWord node is reached, replace with that prefix.
   • If a child is missing, keep the original word.
3. Join the words with spaces.

Correctness sketch

• Invariant: the first isWord encountered along the trie path is the shortest valid replacement.
• Each node represents a prefix; inserting builds all prefixes for a word.
• Searching follows the unique path for the word/prefix.
• Wildcards branch over all possible children, covering all matches.

Trace (hand walkthrough)

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

Walk:
- "cattle" -> shortest root "cat"
- "rattled" -> "rat"; "battery" -> "bat"
- sentence becomes "the cat was rat by the bat"

Pitfalls to avoid

• Replacing with a longer root when a shorter root exists.
• Rebuilding the trie for each word.

Complexity

• Time: O(total characters).
• Extra space: O(total characters) for the trie.

Implementation notes (Go)

• Split the sentence using strings.Fields.
• Use a fixed-size [26]*Node array for children if inputs are lowercase a-z.