Coding Interview PatternsReplace Words
MediumTrie

Replace Words

Explanation & Solution

Practice Problem

Description

In English, we have a concept called root, which can be followed by some other word to form another longer word — let us call that word a derivative. For example, when the root "help" is followed by "ful", we can form a derivative "helpful".

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Input:dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
0
cat
1
bat
2
rat

Output: "the cat was rat by the bat"

Explanation: "cattle" is replaced by "cat" (root), "rattled" is replaced by "rat", and "battery" is replaced by "bat".

Constraints

  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • dictionary[i] consists of only lowercase letters
  • 1 <= sentence.length <= 10⁶
  • sentence consists of only lowercase letters and spaces
  • The number of words in sentence is in the range [1, 1000]
  • The length of each word in sentence is in the range [1, 1000]
  • Every two consecutive words in sentence will be separated by exactly one space
  • sentence does not have leading or trailing spaces

Approach

Trie pattern

1. Build a Trie from the Dictionary

  • Create a trie root node
  • For each root word in the dictionary, insert it character by character
  • Mark the end of each root word with isEnd = true

2. Split the Sentence into Words

  • Use split(' ') to break the sentence into individual words
  • Process each word independently

3. Search for the Shortest Root

  • For each word, traverse the trie character by character
  • If we reach a node with isEnd = true, we found the shortest matching root
  • Replace the word with the substring from index 0 to the current position (inclusive)
  • If no matching root is found (the path breaks), keep the original word

4. Reconstruct the Sentence

  • Join all processed words back together with spaces
  • Return the resulting string

Key Insight

  • The trie naturally finds the shortest matching root because we traverse character by character and stop at the first isEnd we encounter
  • Without a trie, we would need to check every root against every word, leading to inefficiency
Time
O(d * k + n * m) where d is dictionary size, k is average root length, n is number of words, and m is average word length
Space
O(d * k) for the trie structure

Solution Code

Previous
Word Search II
Next
Longest Word in Dictionary