LeetCode #648 Medium

Replace Words

Given a dictionary of root words and a sentence, replace every word in the sentence with its shortest root from the dictionary. If a word has no root, leave it unchanged.

triestringshash-table

Open on LeetCode ↗

02

Intuition

For each word in the sentence you need to find the shortest prefix that appears in the dictionary. A hash set works — check every prefix of increasing length — but a trie answers this in a single walk: feed the word character by character, and the first node you hit that is marked as a word-end is the shortest root. You stop immediately, without ever scanning past the shortest match. The trie also naturally handles the case where one root is a prefix of another, because you encounter the shorter root first.

How to spot this pattern

When you need to find the shortest or longest prefix of a string that belongs to a known set, a trie gives you the answer in a single walk. The pattern shows up whenever the problem says 'dictionary of roots', 'prefix matching', or 'replace by shortest match'. Hash sets can simulate this with a loop over prefix lengths, but the trie is the natural fit.

03

Approach

1

Build a trie from the dictionary roots

Insert each root word character by character into a trie. Mark the final node of each root with a flag (or store the root itself). This costs O(total characters in dictionary). The trie compresses shared prefixes, so roots like cat and cattle share the c-a-t path.

2

Walk each sentence word through the trie, stopping at the first root hit

For each word, traverse the trie one character at a time. If the current node is marked as a word-end, you have found the shortest root — use it and stop. If you fall off the trie (character not found), no root exists for this word, so keep the original. This is the key advantage over a hash set approach: you never scan past the shortest match.

3

Reassemble the sentence from replaced words

Collect the replaced (or unchanged) words into a list and join with spaces. The total work is O(total characters in the sentence) for the trie lookups, plus O(total characters in dictionary) for construction. Space is O(dictionary size) for the trie nodes.

04

Solution

▶1class Solution:
▶2    def replaceWords(self, dictionary, sentence):
▶3        trie = {}
▶4        for root in dictionary:
▶5            node = trie
▶6            for ch in root:
▶7                if ch not in node:
▶8                    node[ch] = {}
▶9                node = node[ch]
▶10            node['#'] = True
▶11 
▶12        words = sentence.split()
▶13        result = []
▶14        for word in words:
▶15            node = trie
▶16            prefix = []
▶17            replaced = False
▶18            for ch in word:
▶19                if ch not in node:
▶20                    break
▶21                prefix.append(ch)
▶22                node = node[ch]
▶23                if '#' in node:
▶24                    replaced = True
▶25                    break
▶26            if replaced:
▶27                result.append(''.join(prefix))
▶28            else:
▶29                result.append(word)
▶30        return ' '.join(result)

05

Common pitfalls

Not stopping at the first (shortest) root

✗ Wrong

for ch in word:
    node = node[ch]
    if '#' in node:
        root = longest_so_far

✓ Right

for ch in word:
    node = node[ch]
    if '#' in node:
        return current_prefix

Continuing past the first word-end flag finds longer roots instead of shorter ones. The problem asks for the shortest root, so you must stop at the first hit.

Forgetting to check for missing characters in the trie

✗ Wrong

for ch in word:
    node = node[ch]

✓ Right

for ch in word:
    if ch not in node:
        break
    node = node[ch]

If a character is not in the trie, the word has no root. Without the check you get a KeyError (dict) or NoneType error (object). The word should be kept as-is.

Splitting and rejoining without preserving single spaces

✗ Wrong

return ' '.join(sentence.split(' '))

✓ Right

return ' '.join(sentence.split())

Using split(' ') on a sentence with multiple consecutive spaces creates empty strings in the list, which join preserves as extra spaces. split() handles any whitespace and produces clean tokens.

06

Edge cases

A word has no matching root

The trie walk falls off without hitting a word-end flag. The original word is kept unchanged — no special branch needed.

A root is an exact match for the word, e.g. root cat and word cat

The trie walk reaches the end of the root and sees the word-end flag, so it replaces the word with itself. Functionally a no-op, correctly handled.

Multiple roots match, e.g. roots a and ap for word apple

The trie walk hits the shorter root a first and returns immediately. The longer root is never reached.

07

Complexity

Time

O(D + S)

Space

O(D)

D is total characters in the dictionary, S is total characters in the sentence. The trie stores at most D characters.