648. Replace Words

Quick Identifier

• Topic: tries
• Pattern: Trie
• Difficulty: Medium
• Companies: Google, Amazon, Microsoft, Meta, Apple
• Frequency: Medium
• LeetCode: 648

Quick Sights

• Time Complexity: O(L); output-heavy problems are bounded by the number of generated states.
• Space Complexity: O(total stored characters) excluding the final output unless stated.
• Core Mechanism: You are given a list of roots (short strings) and a sentence of space-separated words. For each word, replace it with the shortest root in the dictionary that is a prefix of that word; if no root is a prefix, keep the word unchanged.

Concept Explanation

You are given a list of roots (short strings) and a sentence of space-separated words. For each word, replace it with the shortest root in the dictionary that is a prefix of that word; if no root is a prefix, keep the word unchanged.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

• Prefix replacement from a static dictionary
• Shortest matching prefix → walk the trie along the word and stop at the first terminal node on that path
• Building the trie once amortizes many lookups

Study Pattern (SDE3+)

• 0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
• Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
• 5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Approaches

• Scan all roots per word — O(words * roots * L) — too slow at scale.
• Sort roots by length then try shortest first — O(R log R + words * L * something) — acceptable but trie is cleaner.
• Trie — insert all roots, then each word walks until missing edge or hitting a root marker.

Optimal Solution

Go

package main

import "strings"

type Trie struct {
	children [26]*Trie
	isRoot   bool
}

func (trie *Trie) insert(root string) {
	node := trie
	for index := range root {
		offset := int(root[index] - 'a')
		if node.children[offset] == nil {
			node.children[offset] = &Trie{}
		}
		node = node.children[offset]
	}
	node.isRoot = true
}

func (trie *Trie) replaceWord(word string) string {
	node := trie
	for index := range word {
		offset := int(word[index] - 'a')
		if node.children[offset] == nil {
			return word
		}
		node = node.children[offset]
		if node.isRoot {
			return word[:index+1]
		}
	}
	return word
}

func replaceWords(roots []string, sentence string) string {
	trie := &Trie{}
	for _, root := range roots {
		trie.insert(root)
	}
	words := strings.Fields(sentence)
	for wordIndex := range words {
		words[wordIndex] = trie.replaceWord(words[wordIndex])
	}
	return strings.Join(words, " ")
}

JavaScript

class Trie {
	constructor() {
		this.children = new Map();
		this.isRoot = false;
	}

	insert(rootWord) {
		let node = this;
		for (let index = 0; index < rootWord.length; index++) {
			const letter = rootWord[index];
			if (!node.children.has(letter)) {
				node.children.set(letter, new Trie());
			}
			node = node.children.get(letter);
		}
		node.isRoot = true;
	}

	replaceWord(word) {
		let node = this;
		for (let index = 0; index < word.length; index++) {
			const letter = word[index];
			if (!node.children.has(letter)) {
				return word;
			}
			node = node.children.get(letter);
			if (node.isRoot) {
				return word.slice(0, index + 1);
			}
		}
		return word;
	}
}

function replaceWords(roots, sentence) {
	const trie = new Trie();
	for (const rootWord of roots) {
		trie.insert(rootWord);
	}
	return sentence
		.split(' ')
		.map((word) => trie.replaceWord(word))
		.join(' ');
}

Walkthrough

Roots ["cat","bat","rat"], sentence "the cattle was rattled by the battery".

Invariant: descending one character at a time, the first node marked isRoot along the token’s prefix yields the shortest dictionary root by construction of the path length.

Edge Cases

• Root equals whole word → replacement identical
• One root is prefix of another — shorter root terminates walk first (insert order does not matter if trie marks both terminals at correct depths)

Pitfalls

• Returning the longest root instead of first hit — wrong problem interpretation
• Splitting sentence incorrectly on multiple spaces—strings.Fields vs Split (match problem contract)

Similar Problems

• 208. Implement Trie — same trie core without sentence glue.
• 211. Design Add and Search Words Data Structure — richer matching rules.
• 1268. Search Suggestions System — prefix-driven completions.

Variants

• Replace with longest root instead — walk full word tracking last terminal seen.
• Case-insensitive or Unicode alphabets → change edge map.

Mind-Map Tags

#trie #prefix #replace #sentence #shortest-match