Replace Words medium
Description
Given a dictionary of roots and a sentence, replace every word in the sentence with the shortest root that is a prefix of it. If no root applies, leave the word unchanged.
Examples
> dictionary = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
# "cattle" -> "cat", "rattled" -> "rat", "battery" -> "bat"Constraints
1 <= dictionary.length <= 1000, root length ≤ 100.1 <= sentence words <= 1000, lowercase + spaces.
Intuition
Build a trie of the roots. For each word in the sentence, walk the trie character by character and stop the instant you hit an end-of-word node — that’s the shortest root prefix, because end-of-word nodes are encountered in increasing length. If you fall off the trie before hitting one, no root applies.
Try it yourself
Build a trie of the roots, then replace each word with the first root prefix you hit. The runtime loads once on your first run, then it’s instant.
Code
“Shortest root” falls out for free from stopping at the first end-of-word. Because you walk from the start of the word, the first end-of-word node you encounter is necessarily the shortest matching root. No comparison needed — the order of the walk does the work.
Analysis
- Time:
O(D)to build (D = total dictionary characters) +O(S)to process the sentence (S = total sentence characters). Each word walk is bounded by its length. - Space:
O(D)for the trie.
Same skin
- Implement Trie — the underlying structure.
- Longest Word in Dictionary — also about end-of-word nodes along a path.
- IP routing / longest-prefix match — the inverse (longest matching prefix) uses the same walk, recording the last end-of-word instead of stopping at the first.