Is Replace Words easy or hard?

Replace Words is considered a medium difficulty problem. The core idea is simple string prefix matching, but identifying the optimal Trie solution and implementing it correctly adds moderate complexity.

How to solve Replace Words in O(n)?

Build a Trie from the dictionary roots, then scan each word in the sentence character by character while traversing the Trie. Stop once a node marked as a root ending is reached. Each character is processed once during traversal, giving linear time relative to the sentence length.

What is the best approach for Replace Words?

The Trie-based prefix search is generally the best approach. It stores all dictionary roots in a prefix tree and allows each sentence word to be checked character by character. The lookup runs in O(S) time where S is the total number of characters in the sentence, making it efficient for large dictionaries with many overlapping prefixes.

What data structure is used in Replace Words?

The most common data structure used is a Trie (prefix tree). It allows efficient prefix lookups while processing each word in the sentence. A HashSet can also be used for a simpler implementation that checks prefixes through constant-time membership lookups.

What is the time complexity of Replace Words?

The optimal Trie solution runs in O(S) time where S is the total number of characters in the sentence. Building the Trie takes O(D * L), where D is the number of dictionary roots and L is the average root length. The HashSet prefix approach typically runs in O(S * L) due to repeated prefix checks.

Replace Words Python or Java solution approach?

In Python, many solutions use a HashSet and build prefixes incrementally for each word. In Java or C++, a Trie is commonly implemented using node objects or arrays of child pointers. Both approaches produce the same output, but the Trie typically scales better for large inputs.

Is Replace Words asked at Google, Amazon, or Meta?

Prefix replacement and Trie-based problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variations that involve prefix dictionaries, autocomplete systems, or word replacement commonly test understanding of Trie data structures and efficient string processing.

Description Solution Video 14:34

648. Replace Words

Medium68.7% acceptance4 companies

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 derivative. For example, when the root "help" is followed by the word "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.

Example 1:

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

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

Constraints:

1 <= dictionary.length <= 1000
1 <= dictionary[i].length <= 100
dictionary[i] consists of only lower-case letters.
1 <= sentence.length <= 10⁶
sentence consists of only lower-case 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.