Replace each word in a sentence with its shortest dictionary root using a trie - walk until is_end=True and return the root prefix found.

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.

Example 1:

Input: dictionary = ["cor","res","bun"], sentence = "the cornfield was resting by the bunker"
Output: "the cor was res by the bun"
Explanation: "cornfield", "resting", and "bunker" are each replaced by the shortest root that is a prefix of them.

Example 2:

Input: dictionary = ["p","q","t"], sentence = "pearl quiet table"
Output: "p q t"
Explanation: single-letter roots match any word starting with that letter.

Constraints:

1 <= dictionary.length <= 500
1 <= dictionary[i].length <= 50
dictionary[i] consists of only lowercase English letters.
1 <= sentence.length <= 5000
sentence consists of only lowercase English letters and spaces.
Every two consecutive words in sentence are separated by exactly one space.
sentence does not have leading or trailing spaces.

Try it

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word: str) -> None:
        pass
    def find_root(self, word: str) -> str:
        pass

def replace_words(dictionary: list[str], sentence: str) -> str:
    pass

Tests

assert replace_words(["cor","res","bun"], "the cornfield was resting by the bunker") == "the cor was res by the bun"

assert replace_words(["p","q","t"], "pearl quiet table") == "p q t"

assert replace_words(["abc"], "xyz") == "xyz"

assert replace_words(["cor"], "cornbread") == "cor"

Hints (3)

Solution Breakdown

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 "cornfield" against roots ["cor", "res", "bun"]: walk c -> o -> r, and r.is_end is True, so return "cor" without ever reading the remaining nfield. 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.

Replace Words

Problem

Solution Breakdown

Discussion