92. Replace Words with Shortest Root
For each word in the sentence, find the shortest dictionary root that is a prefix of that word and replace the word with that root. Keep a word unchanged when no root matches.
Choose the shortest complete root, not the longest matching prefix. Preserve the sentence's original spacing under this course's contract.
Example 1
Input
roots=[cat,bat,rat]; sentence=the cattle was rattled by the battery
Output
the cat was rat by the bat
Explanation: Each token uses the shortest complete dictionary prefix, not merely an existing trie path.
Example 2
Input
roots=[cattle,cat,c,cat]; sentence=" cattle cat dog "
Output
" c c dog "
Explanation: Root c wins independent of insertion order, while all original spaces remain.
Example 3
Input
roots=[]; sentence=" a b "
Output
" a b "
Explanation: No roots exist; spacing and unmatched words remain exact.
Constraints
0 <= dictionary.length <= 1041 <= dictionary[i].length <= 104sum(dictionary[i].length) <= 1050 <= sentence.length <= 105- Roots contain lowercase English letters; use the shortest matching root.
Hints
Hint 1
Root lengths are encountered in increasing order while walking a token.
Hint 2
A trie path is valid only when a terminal is reached.
Hint 3
Scan the full token boundary, stop lookup at its first terminal, and copy separators directly.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
First terminal replaces each complete original token
["cat","bat","rat"]
"the cattle was rattled by the battery"
"the cat was rat by the bat"