Log inSign up
mediumLeetCodeNot Started

Replace Words

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

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 "an" is followed by the other word "other", we can form a derivative "another".

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 shortest root.

Return the sentence after the replacement.

Example 1 · Example 1: The cattle was rattled:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Explanation: - "cattle" replaced by shortest root "cat" - "rattled" replaced by "rat" - "battery" replaced by "bat" Trie Structure: (root) / | \ b c r | | | a a a | | | t*t*t*

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Use Trie for greedy shortest prefix replacement in text streams.
  • Process space-separated tokens in linear time.
  • Recognize the early-exit advantage of Trie traversal vs hash set prefix slicing.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Replace words by their shortest prefix from a dictionary.
  • High volume of words in a sentence needing prefix checks.
  • Prefix matching priority over full string matching.

Algorithmic Decision Tree:

  • Insert all roots into a Trie.
  • For each sentence word, walk the Trie accumulating characters.
  • On first isEnd == true, return accumulated prefix; on null pointer, return original word.

Connected Patterns:

Implement Trie (Prefix Tree)Longest Word in DictionaryWord Search II

1. Scan All Roots per Word

Intuition

Split sentence into words. For each word, find all roots where word.startsWith(root). Select the shortest root. Join back into a sentence.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Split sentence by spaces.
  2. Step 2: For each word, find all roots starting the word.
  3. Step 3: If multiple, pick shortest root; else keep original word.
  4. Step 4: Join words with space and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <sstream>
5using namespace std;
6
7class Solution {
8public:
9 string replaceWords(vector<string>& dictionary, string sentence) {
10 stringstream ss(sentence);
11 string word, result = "";
12
13 while (ss >> word) {
14 string best = word;
15 for (const string& root : dictionary) {
16 if (word.rfind(root, 0) == 0) {
17 if (root.length() < best.length()) {
18 best = root;
19 }
20 }
21 }
22 if (!result.empty()) result += " ";
23 result += best;
24 }
25 return result;
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<string> dict = {"cat","bat","rat"};
32 string s = "the cattle was rattled by the battery";
33 cout << sol.replaceWords(dict, s) << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(W * D * L) — Compares each of W words against all D roots.
  • Space complexity: O(Sentence Length) — Stores split words array.

Why Brute Force Doesn't Scale:

With 1,000 words and 1,000 roots, checking takes 106 comparisons.

Trie matches each word in O(Root length) steps, completing in ~8ms.

2. Hash Set Prefix Slicing

Intuition

Store roots in unordered_set<string>. For each word in the sentence, test prefixes of length 1, 2, ... up to word.length(). The first prefix found in the set is guaranteed to be the shortest root.

When to apply: Fast to implement when word length is short.

Algorithm

  1. Step 1: Put all roots in a hash set.
  2. Step 2: For each word, loop prefix length k from 1 to word.length().
  3. Step 3: If set.count(word.substr(0, k)), replace word with prefix and break.
  4. Step 4: Join words into result sentence.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <sstream>
5#include <unordered_set>
6using namespace std;
7
8class Solution {
9public:
10 string replaceWords(vector<string>& dictionary, string sentence) {
11 unordered_set<string> dict(dictionary.begin(), dictionary.end());
12 stringstream ss(sentence);
13 string word, result = "";
14
15 while (ss >> word) {
16 string replacement = word;
17 for (size_t k = 1; k <= word.length(); k++) {
18 string pref = word.substr(0, k);
19 if (dict.count(pref)) {
20 replacement = pref;
21 break;
22 }
23 }
24 if (!result.empty()) result += " ";
25 result += replacement;
26 }
27 return result;
28 }
29};
30
31int main() {
32 Solution sol;
33 vector<string> dict = {"cat","bat","rat"};
34 string s = "the cattle was rattled by the battery";
35 cout << sol.replaceWords(dict, s) << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(Sentence Words * L^2) — For each word, slices up to L prefixes and computes their hashes.
  • Space complexity: O(Dictionary Words * L) — Hash set holds all dictionary roots.

3. Trie Shortest Root Replacement

Intuition

Insert all dictionary roots into a Trie. For each word in the sentence, walk down the Trie from root. At each step, if curr.isEnd == true, return the accumulated prefix (guaranteed shortest). If curr.children[idx] == null, break and return original word.

When to apply: Standard optimal solution required in production text-processing pipelines.

Algorithm

  1. Step 1: Build TrieNode with children[26] and boolean isEnd.
  2. Step 2: Insert all roots into the Trie.
  3. Step 3: Define findRoot(word): walk from root. At each char, append to prefix. If curr.children[idx] == null, return original word. Move curr. If curr.isEnd, return prefix.
  4. Step 4: For each word in sentence, replace with findRoot(word).
  5. Step 5: Join words with space and return.

Interactive Trace for Shortest Root Replacement

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Inspect word 'cattle'
Visual state
Values and pointers at this exact step
tree
Root
(root)
char 'c'
'c'

Node order shown; add connections to display explicit tree edges.

curr: c
Check / comparison
child['c'] exists
Decision / next transition
Move to node 'c'. Accumulated: 'c'.
Why this step matters

Step 1: Inspect word cattle. Start at root. Follow child c.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <sstream>
5using namespace std;
6
7struct TrieNode {
8 TrieNode* children[26];
9 bool isEnd;
10 TrieNode() : isEnd(false) {
11 for (int i = 0; i < 26; i++) children[i] = nullptr;
12 }
13};
14
15class Solution {
16 TrieNode* root;
17
18 void insert(const string& word) {
19 TrieNode* curr = root;
20 for (char c : word) {
21 int idx = c - 'a';
22 if (!curr->children[idx]) curr->children[idx] = new TrieNode();
23 curr = curr->children[idx];
24 }
25 curr->isEnd = true;
26 }
27
28 string findRoot(const string& word) {
29 TrieNode* curr = root;
30 string prefix = "";
31 for (char c : word) {
32 int idx = c - 'a';
33 if (!curr->children[idx]) return word;
34 curr = curr->children[idx];
35 prefix += c;
36 if (curr->isEnd) return prefix;
37 }
38 return word;
39 }
40
41public:
42 string replaceWords(vector<string>& dictionary, string sentence) {
43 root = new TrieNode();
44 for (const string& r : dictionary) insert(r);
45
46 stringstream ss(sentence);
47 string word, result = "";
48 while (ss >> word) {
49 if (!result.empty()) result += " ";
50 result += findRoot(word);
51 }
52 return result;
53 }
54};
55
56int main() {
57 Solution sol;
58 vector<string> dict = {"cat","bat","rat"};
59 string s = "the cattle was rattled by the battery";
60 cout << "Optimal replace: " << sol.replaceWords(dict, s) << endl;
61 return 0;
62}

Time & Space Complexity

  • Time complexity: O(Dict Chars + Sentence Chars) — Building Trie is linear in dictionary characters. Each word in the sentence is scanned at most once up to root length.
  • Space complexity: O(Dict Chars * 26) — Trie nodes allocate 26 pointers each.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Check All Roots per WordO(W * D * L)O(1)For each word in sentence, iterate through all D roots and check word.startsWith(root). Track shortest.Iterating entire dictionary for each word.
2.Better — Hash Set of Roots with Prefix SlicingO(W * L^2)O(D * L)Insert roots into a hash set. For each word, slice prefixes of length 1 to L; return first prefix found in set.Substring copies at every character.
3.Optimal — Trie Shortest Prefix MatchOptimalO(Dict Chars + Sentence Chars)O(Dict Chars * 26)Insert roots into Trie. Stream sentence words down the Trie: stop at first isEnd = true in O(Root length) time.None. Canonical Trie text-processing problem.

Common Pitfalls & Crucial Edge Cases

Continuing after finding first root

Continuing deeper into the Trie might find a longer root instead of the required shortest root.

Modifying string during tokenization

Leading/trailing spaces or multiple spaces must be handled safely.

Not returning original word on prefix mismatch

Returning partial prefixes when the complete root does not exist.

Crucial Edge Cases to Validate:

  • Word is already a root in dictionary — Replaces with itself (returns same string).
  • No root matches a word — Word is left completely unchanged.
  • Multiple roots share prefixes ('c', 'ca', 'cat') — First matching root (c) wins because it is the shortest.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Highlight that stopping at the first isEnd == true automatically guarantees the shortest root.
  2. Explain the asymptotic advantage: Trie traversal skips redundant character checks as soon as a mismatch or match occurs.
  3. Mention that Trie memory is linear in dictionary size, completely independent of sentence length.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does the Trie algorithm return immediately when encountering node.isEnd == true?

2.What happens if a word has no matching root in the dictionary?

Back to DSA Sheet