Skip to main content

Trie-Based Word Replacement

medium
TrieStringHash TableTrie Prefix Search
Asked atAmazonGoogleMeta

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.