Trie-Based Word Replacement
Problem Description
In botany, a *root* word can replace a longer word if the longer word starts with (is descended from) the root. Given a dictionary of root words and a sentence, replace every word in the sentence with the shortest matching root word from the dictionary. If a word has no matching root, leave it unchanged.
Write a function `replaceWithRoots(rootWords, sentence)` that returns the modified sentence.
**Example 1:**
```
Input:
rootWords = ["cat", "bat", "rat"]
sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
```
**Example 2:**
```
Input:
rootWords = ["fly", "flyer", "sky"]
sentence = "a flyer landed in the skylight area"
Output: "a fly landed in the sky area"
```
Constraints
- 1 <= rootWords.length <= 5000
- 1 <= rootWords[i].length <= 20
- 1 <= sentence.length <= 10^5
- All characters are lowercase English letters or spaces
- sentence contains at least one word
- Words in the sentence are separated by single spaces
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.