How do you solve Replace Words?

Build a Trie from the dictionary roots. For each word in the sentence, traverse the Trie to find the shortest root prefix. If found, replace the word with this root; otherwise, keep the original word. Join all processed words to form the final sentence. This approach achieves O(N + M * K) time complexity, where N is total characters in dictionary, M is number of words in sentence, and K is average word length.

Replace Words

Q: What is the time complexity of Replace Words?

O(N + M * K). Building the Trie takes O(N) time, where N is the sum of lengths of all dictionary words. Searching for prefixes for each of the M words in the sentence takes O(K) time per word, where K is the average length of the words, resulting in O(M * K).

Q: What pattern does Replace Words use?

The Pattern: Trie (Prefix Tree for Efficient Prefix Matching) The Heuristic: When needing to find the shortest prefix from a large dictionary for multiple query words, build a Trie to represent all prefixes, then traverse it per query word to find the earliest prefix match, enabling O(k) prefix search instead of costly repeated string comparisons.

Medium Trie

Problem

Given a dictionary of words and a sentence, replace all successors in the sentence with the shortest root in the dictionary that is a prefix of the word, and return the modified sentence.

1 ≤ dictionary.length ≤ 10⁵
1 ≤ dictionary[i].length ≤ 100
1 ≤ sentence.length ≤ 10⁶
dictionary[i] and sentence consist only of lowercase letters
The sentence consists of words separated by single spaces

Example

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

Output: "the cat was rat by the bat"

The brute-force approach would check each word in the sentence against every root in the dictionary to find the shortest prefix, resulting in a costly O(m * n * k) time complexity where m is the number of words in the sentence, n is the number of roots, and k is the average root length. The optimal approach uses a Trie to efficiently find the shortest prefix for each word. For example, for the word 'cattle', the Trie traversal finds 'cat' as the shortest prefix root, replacing 'cattle' with 'cat'. Similarly, 'rattled' is replaced by 'rat' and 'battery' by 'bat'. This reduces the prefix search to O(k) per word, where k is the length of the word.

Approach

Straightforward Solution

A naive solution checks each word in the sentence against every root in the dictionary to find the shortest prefix. This leads to O(m * n * k) time complexity, which is impractical for large inputs.

Core Observation

The problem reduces to efficiently finding the shortest prefix of each word in the sentence that exists in the dictionary. This is a classic prefix search problem where a Trie data structure excels by enabling prefix queries in O(k) time, where k is the length of the word.

Path to Optimal

Preview

Recognizing the prefix search nature, the dictionary is stored in a Trie, where each node represents a character and may mark the end of a root word…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build a Trie from the dictionary roots. For each word in the sentence, traverse the Trie to find the shortest root prefix…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(N + M * K)

Building the Trie takes O(N) time, where N is the sum of lengths of all dictionary words. Searching for prefixes for each of the M words in the sentence takes O(K) time per word, where K is the average length of the words, resulting in O(M * K).

Space

O(N)

The Trie stores all dictionary words character by character, requiring O(N) auxiliary space proportional to the total length of all dictionary words. The output string space is excluded.

Pattern Spotlight

Trie (Prefix Tree for Efficient Prefix Matching)

When needing to find the shortest prefix from a large dictionary for multiple query words, build a Trie to represent all prefixes, then traverse it per query word to find the earliest prefix match, enabling O(k) prefix search instead of costly repeated string comparisons.

Solution

Python

1class TrieNode:
  def __init__(self):
      self.children = {}
      self.word = None
5
6class Solution:
  def replaceWords(self, dictionary: List[str], sentence: str) -> str:
      root = TrieNode()
9
      for word in dictionary:
          node = root
          for c in word:
              if c not in node.children:
                  node.children[c] = TrieNode()
              node = node.children[c]
          node.word = word
17
      res = []
19
      for word in sentence.split():
          node = root
          replacement = word
23
          for c in word:
              if c not in node.children:
                  break
              node = node.children[c]
              if node.word:
                  replacement = node.word
                  break
31
          res.append(replacement)
33
      return " ".join(res)

Step-by-Step Solution

Construct Trie from Dictionary Roots

8root = TrieNode()
10for word in dictionary:
  node = root
  for c in word:
      if c not in node.children:
          node.children[c] = TrieNode()
      node = node.children[c]
  node.word = word

Objective

To build a prefix tree that compactly represents all dictionary roots for efficient prefix lookup.

Key Insight

Building a Trie allows shared prefixes among dictionary roots to be stored once, reducing redundant comparisons. Each node holds children nodes keyed by characters and optionally stores a root word when a root ends at that node. This structure enables fast prefix queries by traversing character by character.

Interview Quick-Check

Core Logic

Insert each root word into the Trie by creating or traversing child nodes for each character, marking the end node with the root word.

Common Pitfalls & Bugs

Forgetting to mark the end of a root word in the Trie node leads to incorrect prefix matches.

Traverse Trie to Replace Words with Shortest Prefix

To find and replace each word in the sentence with its shortest root prefix from the Trie, if such a prefix exists.

Join Replaced Words to Form Final Sentence

To combine all processed words into a single string representing the modified sentence.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 4 Critical

self.word = None

Initialize the word attribute to None to mark the end of a root word.

Storing the root word at the terminal node allows quick identification of prefix matches during traversal.

Line 16 Critical

node.word = word

Mark the end of the root word by storing it in the node.

This marks the node as a valid root prefix, enabling early prefix detection during search.

Line 28 Critical

if node.word:

Check if the current node marks the end of a root word.

Finding a node with a stored root word indicates a valid prefix match has been found.

Full line-by-line criticality + rationale for all 23 lines available on Pro.

Test Your Understanding

Why does using a Trie improve prefix search efficiency compared to checking each root against every word?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Replace Words from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Replace Words drill

or drill a free problem

1	`class TrieNode:`
2	`def __init__(self):`
3	`self.children = {}`
4	`self.word = None`
5
6	`class Solution:`
7	`def replaceWords(self, dictionary: List[str], sentence: str) -> str:`
8	`root = TrieNode()`
9
10	`for word in dictionary:`
11	`node = root`
12	`for c in word:`
13	`if c not in node.children:`
14	`node.children[c] = TrieNode()`
15	`node = node.children[c]`
16	`node.word = word`
17
18	`res = []`
19
20	`for word in sentence.split():`
21	`node = root`
22	`replacement = word`
23
24	`for c in word:`
25	`if c not in node.children:`
26	`break`
27	`node = node.children[c]`
28	`if node.word:`
29	`replacement = node.word`
30	`break`
31
32	`res.append(replacement)`
33
34	`return " ".join(res)`

8	`root = TrieNode()`
10	`for word in dictionary:`
11	`node = root`
12	`for c in word:`
13	`if c not in node.children:`
14	`node.children[c] = TrieNode()`
15	`node = node.children[c]`
16	`node.word = word`