Problem Statement

Replace Words

A "root" is a small starting word, like "help". If you stick more letters on the end, you get a longer word called a "derivative", like "helpful". This problem gives you a list of roots (the dictionary) and a sentence. For every word in the sentence, if one of the roots is the beginning of that word, swap the word out for the root. If more than one root could work, use the shortest one. Then return the rebuilt sentence. The tool we use is a Trie. A Trie (say "try") is a tree of letters, like a branching map where each step down spells out one more letter of a word. Picture a family tree of spellings: the root of the tree is empty, and each path from the top spells out a word. It fits perfectly here because to check a word against every root at once, we just walk down the tree letter by letter and stop the moment we land on a spot that finishes a real root.

mediumTrieStringTrieTime: O(n * m) · Space: O(n * m)

Signals to notice

replace words with their shortest rootprefix matchingmultiple roots to check

Brute force first

For each word, check every root to see if it's a prefix. Repeats prefix checks redundantly. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.

The key insight

Build a trie from all roots. For each word in the sentence, walk the trie character by character — the first node marked as a word end is the shortest root. If found, replace the word with the root. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `dictionary=["cat","bat","rat"], sentence="the cattle was rattled by the battery"`

Build trie: insert c-a-t*, b-a-t*, r-a-t* (* = endOfWord); root.children = {c,b,r}. Split sentence into 7 words: [the, cattle, was, rattled, by, the, battery].
"the": i=0 c='t'; 't' not in root.children {c,b,r} -> return word, keep "the".
"cattle": c->a->t; after 't' at i=2 cur.endOfWord=True -> return word[:3]="cat".
"was": i=0 c='w'; 'w' not in root.children -> return word, keep "was".
"rattled": r->a->t; endOfWord at i=2 -> return word[:3]="rat".
"by": 'b' in root, then 'y' not in children of 'b' -> keep "by". "the": 't' not in root -> keep "the".
"battery": b->a->t; endOfWord at i=2 -> return word[:3]="bat".
Join results with spaces -> "the cat was rat by the bat".

What must stay true

The trie naturally finds the shortest prefix match — the first end-marked node during traversal is the shortest root. No need to check all roots explicitly. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

build trie: for each root word, insert chars, mark last node endOfWord
for each word in sentence.split(" "):
    cur = trie root
    walk chars of word; if char missing -> keep word
    if cur.endOfWord after a char -> use word[:i+1] (shortest root)
join replaced words with spaces

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not stopping at the shortest root — if 'a' and 'app' are both roots, 'apple' should be replaced with 'a', not 'app'. The trie walk stops at the first terminal node. The fix is usually to return to the meaning of each move, not just the steps themselves.

Trie Pattern