Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 <= 106sentence consists of only lower-case letters and spaces.sentence is in the range [1, 1000]sentence is in the range [1, 1000]sentence will be separated by exactly one space.sentence does not have leading or trailing spaces.Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Trie
["cat","bat","rat"] "the cattle was rattled by the battery"
["a","b","c"] "aadsfasf absbs bbab cadsfafs"
implement-trie-prefix-tree)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #648: Replace Words
class Solution {
public String replaceWords(List<String> dictionary, String sentence) {
Set<String> s = new HashSet<>(dictionary);
String[] words = sentence.split(" ");
for (int i = 0; i < words.length; ++i) {
String word = words[i];
for (int j = 1; j <= word.length(); ++j) {
String t = word.substring(0, j);
if (s.contains(t)) {
words[i] = t;
break;
}
}
}
return String.join(" ", words);
}
}
// Accepted solution for LeetCode #648: Replace Words
type Trie struct {
children [26]*Trie
ref int
}
func newTrie() *Trie {
return &Trie{ref: -1}
}
func (this *Trie) insert(w string, i int) {
node := this
for _, c := range w {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = newTrie()
}
node = node.children[idx]
}
node.ref = i
}
func (this *Trie) search(w string) int {
node := this
for _, c := range w {
idx := c - 'a'
if node.children[idx] == nil {
return -1
}
node = node.children[idx]
if node.ref != -1 {
return node.ref
}
}
return -1
}
func replaceWords(dictionary []string, sentence string) string {
trie := newTrie()
for i, w := range dictionary {
trie.insert(w, i)
}
ans := strings.Builder{}
for _, w := range strings.Split(sentence, " ") {
if idx := trie.search(w); idx != -1 {
ans.WriteString(dictionary[idx])
} else {
ans.WriteString(w)
}
ans.WriteByte(' ')
}
return ans.String()[:ans.Len()-1]
}
# Accepted solution for LeetCode #648: Replace Words
class Trie:
def __init__(self):
self.children: List[Trie | None] = [None] * 26
self.ref: int = -1
def insert(self, w: str, i: int):
node = self
for c in w:
idx = ord(c) - ord("a")
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.ref = i
def search(self, w: str) -> int:
node = self
for c in w:
idx = ord(c) - ord("a")
if node.children[idx] is None:
return -1
node = node.children[idx]
if node.ref != -1:
return node.ref
return -1
class Solution:
def replaceWords(self, dictionary: List[str], sentence: str) -> str:
trie = Trie()
for i, w in enumerate(dictionary):
trie.insert(w, i)
ans = []
for w in sentence.split():
idx = trie.search(w)
ans.append(dictionary[idx] if idx != -1 else w)
return " ".join(ans)
// Accepted solution for LeetCode #648: Replace Words
struct Solution;
use std::collections::HashMap;
#[derive(Default)]
struct Trie {
children: HashMap<char, Trie>,
end: bool,
}
impl Trie {
fn new() -> Self {
Trie::default()
}
fn insert(&mut self, s: String) {
let mut link = self;
for c in s.chars() {
link = link.children.entry(c).or_default();
}
link.end = true;
}
fn map<'a>(&self, s: &'a str) -> &'a str {
let mut link = self;
for (size, c) in s.char_indices() {
if link.end {
return &s[0..size];
}
if let Some(next) = link.children.get(&c) {
link = next;
} else {
break;
}
}
s
}
}
impl Solution {
fn replace_words(dict: Vec<String>, sentence: String) -> String {
let mut trie = Trie::new();
for word in dict {
trie.insert(word);
}
sentence
.split_whitespace()
.map(|s| trie.map(s))
.collect::<Vec<&str>>()
.join(" ")
}
}
#[test]
fn test() {
let dict = vec_string!["cat", "bat", "rat"];
let sentence = "the cattle was rattled by the battery".to_string();
let res = "the cat was rat by the bat".to_string();
assert_eq!(Solution::replace_words(dict, sentence), res);
}
// Accepted solution for LeetCode #648: Replace Words
class Trie {
#children: Record<string, Trie> = {};
#ref = -1;
insert(w: string, i: number) {
let node: Trie = this;
for (const c of w) {
node.#children[c] ??= new Trie();
node = node.#children[c];
}
node.#ref = i;
}
search(w: string): number {
let node: Trie = this;
for (const c of w) {
if (!node.#children[c]) {
return -1;
}
node = node.#children[c];
if (node.#ref !== -1) {
return node.#ref;
}
}
return -1;
}
}
function replaceWords(dictionary: string[], sentence: string): string {
const trie = new Trie();
for (let i = 0; i < dictionary.length; i++) {
trie.insert(dictionary[i], i);
}
return sentence
.split(' ')
.map(w => {
const idx = trie.search(w);
return idx !== -1 ? dictionary[idx] : w;
})
.join(' ');
}
Use this to step through a reusable interview workflow for this problem.
Store all N words in a hash set. Each insert/lookup hashes the entire word of length L, giving O(L) per operation. Prefix queries require checking every stored word against the prefix — O(N × L) per prefix search. Space is O(N × L) for storing all characters.
Each operation (insert, search, prefix) takes O(L) time where L is the word length — one node visited per character. Total space is bounded by the sum of all stored word lengths. Tries win over hash sets when you need prefix matching: O(L) prefix search vs. checking every stored word.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.