Replace Words — Trie for Shortest Root Replacement

Problem Statement#

LeetCode 648 — Replace Words | Difficulty: Medium

In English, we have a concept called a root, which can be followed by some other word to form another longer word — let us call this word a derivative. For example, when the root "help" is followed by the word "ful", we can form a derivative "helpful".

Given a dictionary of roots and a sentence of words separated by spaces, replace every derivative in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root with the shortest length. Return the modified sentence.

Constraints:

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• 1 <= sentence.length <= 10^6
• The sentence consists of words separated by single spaces.

Examples:

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

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"

Why This Problem Matters#

This is the tutorial problem for "shortest matching prefix" — a pattern that powers URL routers, command palettes, and DNS prefix matching. Every time a system says "shortest match wins", it is doing exactly what this problem does.

Replace Words is asked at Amazon, Google, and Bloomberg as a warm-up to harder trie problems because it tests a single concept cleanly: walk the trie until you hit an isEnd, then stop. The naive O(N times M times L) approach (for each word, scan all roots) becomes O((N + M) times L) with a trie — a big win for large dictionaries.

The Core Insight#

Two-step pipeline:

1. Build a trie from the root dictionary, marking each terminal with isEnd = True.
2. For each word in the sentence, walk the trie one character at a time. The moment you land on a node with isEnd = True, that prefix is the shortest matching root — return it. If the walk dies (missing child) before any isEnd, return the original word unchanged.

The "shortest" requirement is automatically handled because we descend in order and return on the first isEnd we encounter. We never look deeper.

This is dramatically faster than checking each root individually because shared prefixes (e.g. cat, cats, catalog) only get walked once.

Visual Dry Run#

Dictionary: ["cat","bat","rat"]. Trie:

root
├── c → a → t (isEnd)
├── b → a → t (isEnd)
└── r → a → t (isEnd)

Sentence word: "cattle"

Step 1: ch='c', root → c node
Step 2: ch='a', c → a node
Step 3: ch='t', a → t node, t.isEnd=TRUE → return "cat"

Sentence word: "the"

Step 1: ch='t', root has no child 't' → return original "the"

Sentence word: "battery"

Step 1: ch='b', root → b
Step 2: ch='a', b → a
Step 3: ch='t', a → t, isEnd=TRUE → return "bat"

The walk terminates at depth 3 every time — independent of how many roots are in the dictionary.

Solution (Optimal) — Trie Walk#

Python#

class TrieNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Solution:
    def replaceWords(self, dictionary: list[str], sentence: str) -> str:
        # Build trie
        root = TrieNode()
        for w in dictionary:
            node = root
            for ch in w:
                node = node.children.setdefault(ch, TrieNode())
            node.is_end = True
 
        def shortest_root(word: str) -> str:
            node = root
            for i, ch in enumerate(word):
                if ch not in node.children:
                    return word          # no root prefix
                node = node.children[ch]
                if node.is_end:
                    return word[: i + 1]  # shortest match
            return word                  # word itself is a root
 
        return " ".join(shortest_root(w) for w in sentence.split())

JavaScript#

var replaceWords = function (dictionary, sentence) {
  const root = {};
  for (const w of dictionary) {
    let node = root;
    for (const ch of w) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.isEnd = true;
  }
 
  const shortestRoot = (word) => {
    let node = root;
    for (let i = 0; i < word.length; i++) {
      const ch = word[i];
      if (!node[ch]) return word;
      node = node[ch];
      if (node.isEnd) return word.slice(0, i + 1);
    }
    return word;
  };
 
  return sentence.split(" ").map(shortestRoot).join(" ");
};

Complexity#

• Build: O(sum of root lengths).
• Query: O(L) per word, L being the word length.
• Total: O(sum of dictionary chars + sum of sentence chars).
• Space: O(sum of dictionary chars).

Common Mistakes#

1. Returning the longest root instead of shortest — caused by walking the full word before checking isEnd. Always check immediately after descending.
2. Forgetting to handle words with no matching root — the function must return the original word, not an empty string.
3. Splitting the sentence with regex when single-space split suffices — adds overhead.
4. Building the trie inside the per-word loop — turns the algorithm O(N times M).
5. Using a sorted dictionary and linear scan — works but is O(N times log M) per word; the trie is asymptotically better and simpler.
6. Off-by-one when slicing the prefix — word[:i+1] includes the current char; word[:i] does not.

Interview Tips#

• State the trie pattern up front: "build the dictionary as a trie, then for each sentence word walk until isEnd or dead-end."
• Mention that the answer is automatically shortest because we return on first hit.
• Compare to hash-set lookup of every prefix length: O(L) lookups times O(L) hashing = O(L^2) per word. Trie is O(L).
• If the interviewer asks how you would handle case insensitivity or punctuation, mention normalising input before lookup.
• Discuss memory: 1000 roots times 100 chars caps the trie at 100k nodes, totally fine.

Follow-up Questions#

• What if multiple sentences share the same dictionary? Build the trie once and reuse for all sentences — perfect for batch processing.
• What if you also need the longest matching root? Continue walking past the first isEnd, remember the deepest isEnd found, return that.
• What about case-insensitive matching? Lowercase both dictionary and input on insert and query.
• Streaming input? Process word by word as they arrive; the trie is read-only at query time.
• What if roots can also be substrings, not just prefixes? That becomes the Aho-Corasick problem — augment the trie with failure links.

Key Takeaways#

• Replace Words is the "shortest matching prefix" template — return on first isEnd.
• Trie reduces O(N times M) to O((N + M) times L) — massive on large dictionaries.
• The trie gives shortest match for free because of in-order descent.
• Always restore the original word when no root matches; never return empty.
• This pattern powers URL routers, autocomplete, and longest-prefix-match in routing tables.
• A clean warm-up before tackling LC 212 Word Search II or LC 472 Concatenated Words.