#648 Replace Words

frequently reported atByteDance / TikTok Microsoft Google

the problem

In plain words

Given a dictionary of roots and a sentence, replace every word in the sentence by the shortest root that is a prefix of it. Words with no root stay unchanged.

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

out "the cat was rat by the bat"

in dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"

out "a a b c"

1 ≤ dictionary.length ≤ 1000
1 ≤ dictionary[i].length ≤ 100
1 ≤ sentence.length ≤ 10⁶
Words separated by single spaces

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTrie (prefix tree)

Walk each word down a trie of roots. The first end-of-word node you hit is the shortest root — no need to try every prefix length.

solutions

From brute force to optimal

For each word, check prefixes of length 1, 2, 3, … against a set of roots; the first hit is the shortest.

roots = new HashSet<>(dictionary).
For each word, for len = 1..L: if roots contains word[0..len) → replace and stop.

timeO(D + Σ L²)

Each prefix check builds a substring and hashes it: O(len) each, up to L checks per word (D = letters in the dictionary).

spaceO(D + n)

The set of roots and the split sentence.

javajava.util.*

1class Solution {2    public String replaceWords(List<String> dictionary, String sentence) {3        Set<String> roots = new HashSet<>(dictionary);4        String[] words = sentence.split(" ");5        for (int w = 0; w < words.length; w++) {6            for (int len = 1; len <= words[w].length(); len++) {   // shortest prefix first7                String prefix = words[w].substring(0, len);         // O(len) copy + hash8                if (roots.contains(prefix)) {9                    words[w] = prefix;10                    break;11                }12            }13        }14        return String.join(" ", words);15    }16}

Insert all roots in a trie. For each word, walk letter by letter and stop at the first node with isEnd.

Build the trie of roots.
For each word: walk; if a child is missing → keep the word; if isEnd → output the prefix so far.
Join with spaces.

timeO(D + n)

Each dictionary letter is inserted once, and each sentence letter is visited at most once (n = sentence length).

spaceO(D·26 + n)

Trie nodes plus the output string.

javajava.util.*

1class Solution {2    private static class Node {3        Node[] children = new Node[26];4        boolean isEnd;5    }6 7    public String replaceWords(List<String> dictionary, String sentence) {8        Node root = new Node();9        for (String r : dictionary) {10            Node cur = root;11            for (char ch : r.toCharArray()) {12                int i = ch - 'a';13                if (cur.children[i] == null) cur.children[i] = new Node();14                cur = cur.children[i];15            }16            cur.isEnd = true;17        }18        StringBuilder out = new StringBuilder();19        for (String word : sentence.split(" ")) {20            if (out.length() > 0) out.append(' ');21            out.append(shortestRoot(root, word));22        }23        return out.toString();24    }25 26    /** Walk the word; the first end-of-word node we meet is the shortest root. */27    private String shortestRoot(Node root, String word) {28        Node cur = root;29        for (int i = 0; i < word.length(); i++) {30            cur = cur.children[word.charAt(i) - 'a'];31            if (cur == null) return word;                  // no root fits: keep the word32            if (cur.isEnd) return word.substring(0, i + 1);33        }34        return word;35    }36}

in the room

How to say it in the interview

talk track

Point out that the trie gives the shortest root for free: we stop at the first end flag, which is the shortest by construction.

traps

Stopping at the longest root instead of the shortest.
Building the result with += in a loop — O(n²) copying; use a StringBuilder or String.join.

what they ask next

Follow-ups

Replace each word by the longest root instead?

Keep walking past end nodes and remember the last one you saw. Stop at a missing child or the end of the word, then use that last root (or the word if there was none). Still O(D + n).

New roots are added between sentences?

Insert each new root into the same trie in O(its length). Nothing needs rebuilding.

before you submit

Edge cases to test

Nested roots ("a", "aa", "aaa") → always the shortest, "a".
A root longer than the word ("catalogue" vs "cat") → no replacement.
No root fits any word → the sentence comes back unchanged.

practise next