Replace Words

medium

Replace words in a sentence by the shortest dictionary root

Replace Words

Key Insight

Insert all roots first, then for each sentence word return first prefix that is terminal in the trie.

Step 1Build Root Set
Array
cat
0
bat
1
rat
2
HashMap
cat:3
bat:3
rat:3

Insert cat, bat, rat into trie.

1 / 3

Learn the Pattern

Hash MapUse a hash map for O(1) lookup to track seen elements, frequencies, or complement values during array traversal.
Practice the Code

Step-by-Step Walkthrough: Replace Words

Insert all roots first, then for each sentence word return first prefix that is terminal in the trie.

  1. Build Root Set

    Insert cat, bat, rat into trie.

  2. Replace Each Token

    For "cattle", scan chars and stop at first terminal root "cat".

  3. Final Sentence

    Only words with no matching root stay unchanged.