441. Replace Words
Call a short word a root if longer words can be built from it by appending letters — the root help builds helpful, for instance. You are given a list dictionary of roots and a sentence whose words are separated by single spaces.
Rewrite the sentence so that every word built from some root is cut back down to that root. When a word can be built from more than one root, use the shortest such root (it is unique — two different roots of equal length cannot both begin the same word). Words that no root builds are kept as they are.
Your function receives dictionary and sentence and returns the rewritten sentence as a single string with words separated by single spaces.
Example 1:
Input: dictionary = ["cat", "bat", "rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Explanation: "cattle" begins with the root "cat", "rattled" with "rat", and "battery" with "bat"; the other words match no root and stay unchanged.
Example 2:
Input: dictionary = ["a", "b", "c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"
Explanation: Every word starts with one of the single-letter roots, so each collapses to that one letter.
Constraints:
- 1 ≤ dictionary.length ≤ 1000
- 1 ≤ dictionary[i].length ≤ 100
- The sentence contains between 1 and 1000 words separated by single spaces, each word 1 to 100 characters.
- All roots and words consist of lowercase English letters only.
Hints:
For a single word, the candidate roots are exactly its prefixes. Check the word's prefixes from shortest to longest against a set of roots and stop at the first hit.
A trie makes that prefix probe one walk: insert every root, then trace each word letter by letter — the first node marked end-of-root is the shortest root, and falling off the trie means no root exists.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: dictionary = ["cat", "bat", "rat"], sentence = "the cattle was rattled by the battery"
Expected output: "the cat was rat by the bat"