Replace Words solution and explanation
Google
9 more videos on this problem
Replace Words | Using HashSet | Uber | Leetcode 648 | codestorywithMIKcodestorywithMIK · 14:34 · 9K views
Replace Words | Using TRIE | Uber | Leetcode 648 | codestorywithMIKcodestorywithMIK · 22:49 · 7K views
Replace Words | Leetcode 648Pepcoding · 31:44 · 5K views
648. Replace Words | LEETCODE MEDIUM | HASH SET | CODE EXPLAINER | LEETCODEcode Explainer · 6:53 · 5K views
✅ Replace Words - LeetCode 648 - Strings - Tries - Explained in Detail - Interview SolutionLeet Logics · 15:13 · 2K views
Leetcode 648 Replace WordsRen Zhang · 15:12 · 1K views
648. Replace Words (Leetcode Medium)Programming Live with Larry · 14:23 · 1K views
Daily Leetcode #1529: Jun 07, 2024 - 648. Replace WordsProgramming Live with Larry · 28:36 · 699 views
Replace Word - Leetcode 648 - Trie - PythonEffective Coder · 18:55 · 610 views
Leetcode-648. Replace Words | Trie SeriesRaman Bhari · 27:56 · 580 views
The problem
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 <= 10001 <= dictionary[i].length <= 100dictionary[i]consists of only lower-case letters.1 <= sentence.length <= 106sentenceconsists of only lower-case letters and spaces.- The number of words in
sentenceis in the range[1, 1000] - The length of each word in
sentenceis in the range[1, 1000] - Every two consecutive words in
sentencewill be separated by exactly one space. sentencedoes not have leading or trailing spaces.
Approach overview
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.
Approach 1: Using HashSet for Quick Search
Store all roots in a HashSet. This allows for O(1) average time complexity when checking if a root exists. For each word in the sentence, check each prefix to determine if it is a root. As soon as you find a root, replace the word with this root.
def replaceWords(dictionary, sentence):
rootSet = set(dictionary)
def replace(word):
for i in range(1, len(word) + 1):
if word[:i] in rootSet:
return word[:i]
return word
return ' '.join(map(replace, sentence.split()))function replaceWords(dictionary, sentence) {
const rootSet = new Set(dictionary);
return sentence.split(' ').map(word => {
for (let i = 1; i <= word.length; i++) {
if (rootSet.has(word.slice(0, i))) {
return word.slice(0, i);
}
}
return word;
}).join(' ');
}This solution creates a set from the given dictionary containing root words. It then splits the sentence into words and attempts to replace each word with its shortest root using the replace() function. For each word, the function checks successive prefixes and returns the prefix (root) if it exists in the set. The replaced words are then joined back into a sentence and returned.
Time Complexity: O(N * M), where N is the number of words in the sentence and M is the length of the longest word.
Space Complexity: O(D), where D is the total length of all the roots.
Approach 2: Using Trie for Prefix Search
Build a Trie from the given dictionary of roots. A Trie is a tree-like data structure that holds a dynamic set of strings where all keys share a common prefix. For each word in the sentence, traverse through the Trie to find the shortest prefix that matches a segment of the word, if such a prefix exists, it replaces the word.
import java.util.*;
class Solution {
private static class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
String word;
}
private static class Trie {
private TrieNode root = new TrieNode();
void insert(String word) {
TrieNode cur = root;
for (char letter : word.toCharArray()) {
cur = cur.children.computeIfAbsent(letter, k -> new TrieNode());
}
cur.word = word;
}
String searchRoot(String word) {
TrieNode cur = root;
for (char letter : word.toCharArray()) {
cur = cur.children.get(letter);
if (cur == null) return word;
if (cur.word != null) return cur.word;
}
return word;
}
}
public String replaceWords(List<String> dictionary, String sentence) {
Trie trie = new Trie();
for (String root : dictionary) {
trie.insert(root);
}
StringBuilder result = new StringBuilder();
for (String word : sentence.split(" ")) {
if (result.length() > 0) {
result.append(" ");
}
result.append(trie.searchRoot(word));
}
return result.toString();
}
}#include <iostream>
#include <vector>
#include <sstream>
#include <unordered_map>
using namespace std;
struct TrieNode {
unordered_map<char, TrieNode*> children;
string word;
};
class Trie {
public:
TrieNode* root;
Trie() { root = new TrieNode(); }
void insert(string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c)) {
node->children[c] = new TrieNode();
}
node = node->children[c];
}
node->word = word;
}
string searchRoot(const string& word) {
TrieNode* node = root;
for (char c : word) {
if (!node->children.count(c) || node->word.size() > 0) break;
node = node->children[c];
}
return node->word.empty() ? word : node->word;
}
};
string replaceWords(vector<string>& dictionary, string sentence) {
Trie trie;
for (string& root : dictionary) {
trie.insert(root);
}
istringstream iss(sentence);
ostringstream oss;
string word;
bool first = true;
while (iss >> word) {
if (!first) oss << " ";
oss << trie.searchRoot(word);
first = false;
}
return oss.str();
}The Java solution involves constructing a Trie from the root words. Each word in the sentence is processed by traversing the Trie to find matching roots. If no root is found, the original word is used.
Time Complexity: O(D + N * K), D is the sum of lengths of all roots, N is the number of words, K is the length of the longest word.
Space Complexity: O(D), for storing the Trie.
Approach 3: Trie
We can use a trie to store all the roots in the dictionary. Define the trie node class Trie, which contains an array children of length 26 to store child nodes, and a boolean variable is_end to mark whether it is a complete root.
For each root, we insert it into the trie. For each word in the sentence, we search for its shortest root in the trie. If found, we replace the word; otherwise, we keep it unchanged.
The time complexity is O(n times |w| + L), and the space complexity is O(n times |w|), where n and |w| are the number of roots in the dictionary and the average length, respectively, and L is the total length of words in the sentence.
class Trie {
children: Array<Trie | null>;
isEnd: boolean;
constructor() {
this.children = new Array(26).fill(null);
this.isEnd = false;
}
insert(w: string): void {
let node: Trie = this;
for (const c of w) {
const idx = c.charCodeAt(0) - 97;
if (!node.children[idx]) {
node.children[idx] = new Trie();
}
node = node.children[idx]!;
}
node.isEnd = true;
}
search(w: string): string {
let node: Trie = this;
for (let i = 0; i < w.length; i++) {
const idx = w.charCodeAt(i) - 97;
if (!node.children[idx]) {
return w;
}
node = node.children[idx]!;
if (node.isEnd) {
return w.slice(0, i + 1);
}
}
return w;
}
}
function replaceWords(dictionary: string[], sentence: string): string {
const trie = new Trie();
for (const w of dictionary) {
trie.insert(w);
}
return sentence
.split(' ')
.map(w => trie.search(w))
.join(' ');
}type Trie struct {
children [26]*Trie
isEnd bool
}
func (t *Trie) insert(w string) {
node := t
for _, c := range w {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (t *Trie) search(w string) string {
node := t
for i, c := range w {
idx := c - 'a'
if node.children[idx] == nil {
return w
}
node = node.children[idx]
if node.isEnd {
return w[:i+1]
}
}
return w
}
func replaceWords(dictionary []string, sentence string) string {
trie := &Trie{}
for _, w := range dictionary {
trie.insert(w)
}
words := strings.Split(sentence, " ")
for i, w := range words {
words[i] = trie.search(w)
}
return strings.Join(words, " ")
}struct Trie {
children: Vec<Option<Box<Trie>>>,
is_end: bool,
}
impl Trie {
fn new() -> Self {
Self {
children: (0..26).map(|_| None).collect(),
is_end: false,
}
}
fn insert(&mut self, w: String) {
let mut node = self;
for c in w.chars() {
let idx = (c as u8 - b'a') as usize;
node = node.children[idx].get_or_insert(Box::new(Trie::new()));
}
node.is_end = true;
}
fn search(&self, w: &str) -> String {
let mut node = self;
for (i, c) in w.chars().enumerate() {
let idx = (c as u8 - b'a') as usize;
if node.children[idx].is_none() {
return w.to_string();
}
node = node.children[idx].as_ref().unwrap();
if node.is_end {
return w[..i + 1].to_string();
}
}
w.to_string()
}
}
impl Solution {
pub fn replace_words(dictionary: Vec<String>, sentence: String) -> String {
let mut trie = Trie::new();
for w in dictionary {
trie.insert(w);
}
sentence
.split_whitespace()
.map(|w| trie.search(w))
.collect::<Vec<_>>()
.join(" ")
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using HashSet for Quick Search | Time Complexity: O(N * M), where N is the number of words in the sentence and M is the length of the longest word. |
| Using Trie for Prefix Search | Time Complexity: O(D + N * K), D is the sum of lengths of all roots, N is the number of words, K is the length of the longest word. |
| Trie | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Prefix Search | O(S * L) | O(D) | Good for simple implementation when dictionary size is moderate |
| Trie Prefix Search | O(S) | O(D * L) | Best for large dictionaries or heavy prefix matching workloads |
Frequently asked questions
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.