Replace Words

Replace Words

What is this problem about?

The Replace Words interview question gives you a dictionary of root words and a sentence (string of space-separated words). For each word in the sentence, if it starts with any root from the dictionary, replace it with the shortest matching root. If no root matches, keep the word unchanged. Return the modified sentence as a string.

Why is this asked in interviews?

This problem is asked at Uber, Microsoft, Amazon, TikTok, Google, and Bloomberg because it is a direct application of the Trie (prefix tree) data structure. It models real-world scenarios like autocomplete, spell-checkers, and search query normalization. It also has a simpler hash-set approach, giving interviewers the chance to discuss tradeoffs between implementation simplicity and theoretical elegance.

Algorithmic pattern used

The primary pattern is Trie-based prefix matching. Insert all roots into a Trie. For each word in the sentence, traverse the Trie character by character. Stop at the first Trie node marked as an end-of-root — that is the shortest matching root. If no root matches, use the original word. Build the result sentence from the processed words.

The simpler alternative: store roots in a set, then for each word try prefixes of length 1, 2, ... up to min(len(word), max_root_len) and return the first match.

Example explanation

Dictionary: ["cat", "car", "bat"]. Sentence: "the cattle was shot by the carbon bat".

• "the" → no root match → keep "the".
• "cattle" → prefix "cat" is a root → replace with "cat".
• "was" → no match → keep.
• "shot" → no match → keep.
• "carbon" → prefix "car" is a root → replace with "car".
• "bat" → "bat" is itself a root → replace with "bat".

Result: "the cat was shot by the car bat".

Common mistakes candidates make

• Not finding the SHORTEST matching root — if both "cat" and "ca" are roots, "ca" should win.
• Using a list instead of a set or Trie, leading to O(d × w) brute-force lookup.
• Rebuilding the sentence incorrectly by not joining words with spaces.
• Inserting roots into the Trie without marking end-of-root nodes properly.

Interview preparation tip

For the Replace Words coding problem, the Trie and string interview pattern is the optimal solution. Practice Trie insertion and prefix search before the interview. Interviewers at TikTok and Bloomberg may ask "why Trie over a hash set?" — the answer is O(L) lookup per word (L = word length) independent of dictionary size, vs O(L × d) with a set. Know both approaches and be ready to code either one.