Replace Words - Video Solutions

Problem Overview: You receive a dictionary of root words and a sentence. Each word in the sentence should be replaced with the shortest dictionary root that is its prefix. If multiple roots match, the shortest one wins. If no root matches, keep the original word.

The core challenge is efficient prefix detection. For every word in the sentence, you need to determine whether any dictionary root is a prefix. Naively scanning the entire dictionary for every word works but wastes time when the dictionary grows large.

Approach 1: HashSet for Quick Prefix Search (Time: O(S * L), Space: O(D))

Store every root from the dictionary in a HashSet. Then process each word in the sentence one character at a time, building prefixes like w[0:1], w[0:2], w[0:3]. As soon as a prefix exists in the set, replace the word with that prefix. Stop immediately since the first match is the shortest root.

The key insight is constant-time hash lookups. Instead of checking each root against the word, you grow prefixes of the word and check membership in O(1). Limiting checks to the maximum root length avoids unnecessary work. This approach is simple and performs well for moderate dictionary sizes using a hash table combined with string prefix checks.

Approach 2: Trie for Prefix Search (Time: O(S), Space: O(D * L))

Insert every dictionary root into a Trie. Each node represents a character, and a flag marks the end of a root. When processing a sentence word, traverse the Trie character by character. If you hit a node marked as a root ending, you immediately return that prefix. If traversal breaks because the next character does not exist, the word has no valid root replacement.

The Trie structure naturally models prefix relationships. Instead of generating prefixes manually, you follow edges in the tree. Each character is visited once, which gives near linear time relative to the total number of characters in the sentence. This method is the most scalable solution when the dictionary contains many overlapping prefixes and is a classic application of a Trie data structure.

Recommended for interviews: The Trie approach is typically expected in interviews because it demonstrates knowledge of prefix data structures and achieves optimal lookup performance. The HashSet method is still valuable to mention first since it shows you recognize a simpler solution using standard library structures. Showing both approaches proves you understand the tradeoff between implementation complexity and algorithmic efficiency.