Trie
LC #648Medium
Replace Words
Trie
AmazonGoogleProblem
Replace words in a sentence with their shortest root from a dictionary.
triestringhash-map
Constraints
- ›1 ≤ dictionary.length ≤ 1000
- ›1 ≤ dictionary[i].length ≤ 100
- ›sentence contains 1–1000 words separated by single spaces
Example
Input
dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"Output
"the cat was rat by the bat"Why
"cattle" → "cat", "rattled" → "rat", "battery" → "bat"