Replace Words

Problem

Text normalization pipelines reduce inflected words to their roots before indexing - "running" becomes "run", "cats" becomes "cat". Given a dictionary of root words and a sentence, replace each word in the sentence with its shortest matching root from the dictionary. If a word has no matching root, keep it unchanged.

roots = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
→ "the cat was rat by the bat"
 
roots = ["a", "b", "c"]
sentence = "aadsfasf absbs bbab cadsfafs"
→ "a a b c"

Solution

Approach: Trie lookup that stops at the first is_end - the shortest matching root.

Build a trie from every dictionary root with a standard insert. The replacement work happens in find_root, which walks one sentence word character by character from the root, appending each matched character to a prefix accumulator. The key move is the is_end check inside the loop: the instant traversal lands on a node where node.is_end is True, a complete root has been spelled, so it returns "".join(prefix) immediately. Because a trie path deepens one character at a time, the first is_end you hit is always the shallowest - hence the shortest root - which is exactly what the problem asks for. If a character has no matching child the word falls off the trie, so no root is a prefix of it and the original word is returned unchanged; the same return word fires if the loop finishes without ever seeing is_end. Trace "cattle" against roots ["cat", "bat", "rat"]: walk c -> a -> t, and t.is_end is True, so return "cat" without ever reading the remaining tle. replace_words simply splits the sentence, maps find_root over each word, and rejoins with spaces.

Edge cases: A word with no matching root (no first-character edge, or shorter than every root so is_end never fires) is kept verbatim. Duplicate roots are harmless - re-inserting just re-marks an already-is_end node.

Complexity: O(sum of root lengths) to build the trie plus O(sum of word lengths) to process the sentence, O(sum of root lengths) space - each character is visited at most once.