Problem 19.4 · TrieMedium

Replace Words

What it teaches: Shortest-prefix lookup: stop at the first end-of-word node on the path.

Practise it on judges as “Replace Words”.

The problem

Given a dictionary of roots and a sentence, replace every word that starts with some root by the shortest such root. Return the new sentence.

Example 1

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

Constraints

1 ≤ roots ≤ 1000
Sentence up to 10⁶ characters

Pattern clues in the wording

→ Find the shortest dictionary prefix of each word

These clues point to Trie (Prefix Tree): Store words character by character in a tree so every prefix is a path you can walk in O(length).

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        return sentence;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	dictionary = ["cat","bat","rat"] sentence = "the cattle was rattled by the battery"	"the cat was rat by the bat"
2	dictionary = ["a","b","c"] sentence = "aadsfasf absbs bbab cadsfafs"	"a a b c"

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Trie of roots · O(total characters)

Trie of roots

Time O(total characters) Space O(root characters)

Insert roots. For each word, walk the trie; if you reach a root node, use the prefix so far; if the path breaks, keep the word.

Approach 1

import java.util.*;

class Solution {
    private static class Node {
        Node[] next = new Node[26];
        boolean isRoot;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        Node root = new Node();
        for (String w : dictionary) {
            Node n = root;
            for (char c : w.toCharArray()) {
                if (n.next[c - 'a'] == null) n.next[c - 'a'] = new Node();
                n = n.next[c - 'a'];
            }
            n.isRoot = true;
        }
        StringBuilder out = new StringBuilder();
        for (String word : sentence.split(" ")) {
            if (out.length() > 0) out.append(' ');
            out.append(shortestRoot(root, word));
        }
        return out.toString();
    }

    private String shortestRoot(Node root, String word) {
        Node n = root;
        for (int i = 0; i < word.length(); i++) {
            n = n.next[word.charAt(i) - 'a'];
            if (n == null) return word;
            if (n.isRoot) return word.substring(0, i + 1);
        }
        return word;
    }
}

Verdict: Linear in the input.

Before you submit

Edge cases and common mistakes

Test these inputs

Roots that are prefixes of other roots (use the shorter)
Words with no root

Mistakes people make

Checking every root against every word with startsWith (O(roots × words)).

Interview

Follow-up questions

Could a hash set of roots work?

Command Palette

The problem

Approaches

Trie of roots

Edge cases and common mistakes

Follow-up questions