DSA problem
Replace Words
In English, we have a concept called root, which can be followed by some other word to form another longer word — let's call this word a successor. For example, when the root an is followed by the successor word other, we can form a new word another.
Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming them. If a successor can be replaced by more than one root, replace it with the root that has the shortest length. Return the resulting sentence.
A brute-force approach would, for each word in the sentence, scan every root and check whether it is a prefix of the word. That costs O(W * R * L) time for W sentence words, R roots, and average length L — wasteful when roots share prefixes.
A trie compresses the roots so that each word in the sentence is processed in O(L). Build a trie from all roots, marking the terminal node of each inserted root with isEnd = true. Then for every word in the sentence, walk down the trie character by character; the moment you land on an isEnd node, that path is the shortest matching root and you replace the word with the characters consumed so far. If the walk ends without ever hitting an isEnd node, keep the original word unchanged. Stitching the transformed tokens back with spaces produces the answer in O(total characters in sentence + total root characters).
Examples
dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery""the cat was rat by the bat"dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs""a a b c"dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery""the cat was rat by the bat"Constraints
- 1 <= dictionary.length <= 1000
- 1 <= dictionary[i].length <= 100
- dictionary[i] consists of only lowercase English letters.
- 1 <= sentence.length <= 10^6
- sentence consists of only lowercase letters and spaces.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.