164. Replace Words

🔗 LeetCode Problem: 648. Replace Words
📊 Difficulty: Medium
🏷️ Topics: Trie, String, Array, Hash Table

Problem Statement

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

Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the derivatives in the sentence with the root forming it. If a derivative can be replaced by more than one root, replace it with the root that has the shortest length.

Return the sentence after the replacement.

Example 1:

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

Example 2:

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

Example 3:

Input: dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
Output: "a a a a a a a a bbb baba a"

Constraints: - 1 <= dictionary.length <= 1000 - 1 <= dictionary[i].length <= 100 - dictionary[i] consists of only lowercase letters - 1 <= sentence.length <= 10^6 - sentence consists of only lowercase letters and spaces - The number of words in sentence is in the range [1, 1000] - The length of each word in sentence is in the range [1, 1000] - Every two consecutive words in sentence will be separated by exactly one space - sentence does not have leading or trailing spaces

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving:

Dictionary (roots): ["cat", "bat", "rat"]
Sentence: "the cattle was rattled by the battery"

Goal: Replace derivatives with their shortest roots

Word by word analysis:
  "the"     → No root matches → Keep "the"
  "cattle"  → Starts with "cat" → Replace with "cat" ✓
  "was"     → No root matches → Keep "was"
  "rattled" → Starts with "rat" → Replace with "rat" ✓
  "by"      → No root matches → Keep "by"
  "the"     → No root matches → Keep "the"
  "battery" → Starts with "bat" → Replace with "bat" ✓

Result: "the cat was rat by the bat"

KEY INSIGHT: We need PREFIX MATCHING! 🔑

Why Trie is Perfect:

APPROACH 1: Brute Force (Without Trie)
For each word in sentence:
  For each root in dictionary:
    Check if word starts with root
    Keep track of shortest matching root
  Replace word with shortest root (if found)

Problem:
  - m words in sentence
  - n roots in dictionary
  - k = average root length
  - l = average word length

  Time: O(m * n * k) - TOO SLOW! 😰

Example: 1000 words, 1000 roots, each length 10
  = 1000 * 1000 * 10 = 10,000,000 operations!

APPROACH 2: Trie (Optimal)
Build Trie once with all roots: O(n * k)
For each word, search Trie once: O(m * l)

Total: O(n * k + m * l) - MUCH BETTER! 🚀

Example: Same numbers
  = (1000 * 10) + (1000 * 15) = 25,000 operations!

400x faster! 💨

The Trie Magic - Visual Structure:

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

Build Trie:
                root
              /  |  \
            b    c    r
            |    |    |
            a    a    a
            |    |    |
           [t]  [t]  [t]
         (bat) (cat) (rat)

[t] means: isEndOfWord = true (this is a complete root!)

Now search for "cattle":
  Start at root
  c → exists ✓
  a → exists ✓  
  t → exists ✓, and isEndOfWord = true!

  STOP! Found shortest root "cat"! 🎯

  Don't need to check remaining "tle"!

This is why Trie is perfect:
  1. Shares common prefixes (memory efficient)
  2. Stops at first complete root (finds shortest)
  3. Traversal is O(word length), not O(dictionary size)

Complete Visual Walkthrough:

Dictionary: ["cat", "bat", "rat"]
Sentence: "the cattle was rattled by the battery"

STEP 1: Build Trie (ONE TIME)
┌─────────────────────────────────────────────┐
│         Build Trie from Dictionary          │
├─────────────────────────────────────────────┤
│                                             │
│  Insert "cat":                              │
│    root → c → a → t (mark END)              │
│                                             │
│  Insert "bat":                              │
│    root → b → a → t (mark END)              │
│                                             │
│  Insert "rat":                              │
│    root → r → a → t (mark END)              │
│                                             │
│  Final Trie:                                │
│                  root                       │
│                / | \                        │
│               b  c  r                       │
│               |  |  |                       │
│               a  a  a                       │
│               |  |  |                       │
│              [t][t][t]                      │
│                                             │
└─────────────────────────────────────────────┘

STEP 2: Process Each Word
┌─────────────────────────────────────────────┐
│           Word 1: "the"                     │
├─────────────────────────────────────────────┤
│  Search in Trie:                            │
│    root → t? → NOT FOUND ✗                  │
│  Result: Keep "the"                         │
└─────────────────────────────────────────────┘

┌─────────────────────────────────────────────┐
│           Word 2: "cattle"                  │
├─────────────────────────────────────────────┤
│  Search in Trie:                            │
│    root → c → exists ✓                      │
│         → a → exists ✓                      │
│         → t → exists ✓ AND isEnd = true!    │
│                                             │
│  Found root "cat" at position 3             │
│  Stop here! Don't check "tle"               │
│                                             │
│  Result: Replace "cattle" with "cat"        │
└─────────────────────────────────────────────┘

┌─────────────────────────────────────────────┐
│           Word 3: "was"                     │
├─────────────────────────────────────────────┤
│  Search in Trie:                            │
│    root → w? → NOT FOUND ✗                  │
│  Result: Keep "was"                         │
└─────────────────────────────────────────────┘

┌─────────────────────────────────────────────┐
│           Word 4: "rattled"                 │
├─────────────────────────────────────────────┤
│  Search in Trie:                            │
│    root → r → exists ✓                      │
│         → a → exists ✓                      │
│         → t → exists ✓ AND isEnd = true!    │
│                                             │
│  Found root "rat" at position 3             │
│  Stop here! Don't check "tled"              │
│                                             │
│  Result: Replace "rattled" with "rat"       │
└─────────────────────────────────────────────┘

┌─────────────────────────────────────────────┐
│           Word 5: "by"                      │
├─────────────────────────────────────────────┤
│  Search in Trie:                            │
│    root → b → exists ✓                      │
│         → y? → NOT FOUND ✗                  │
│  Result: Keep "by"                          │
└─────────────────────────────────────────────┘

┌─────────────────────────────────────────────┐
│           Word 6: "the"                     │
├─────────────────────────────────────────────┤
│  Search in Trie:                            │
│    root → t? → NOT FOUND ✗                  │
│  Result: Keep "the"                         │
└─────────────────────────────────────────────┘

┌─────────────────────────────────────────────┐
│           Word 7: "battery"                 │
├─────────────────────────────────────────────┤
│  Search in Trie:                            │
│    root → b → exists ✓                      │
│         → a → exists ✓                      │
│         → t → exists ✓ AND isEnd = true!    │
│                                             │
│  Found root "bat" at position 3             │
│  Stop here! Don't check "tery"              │
│                                             │
│  Result: Replace "battery" with "bat"       │
└─────────────────────────────────────────────┘

FINAL RESULT:
  "the cat was rat by the bat" ✨

The "Shortest Root" Property:

Dictionary: ["a", "aa", "aaa"]
Word: "aaaaa"

Search in Trie:
                root
                 |
                [a]  ← isEnd = true (root "a")
                 |
                [a]  ← isEnd = true (root "aa")
                 |
                [a]  ← isEnd = true (root "aaa")

Step 1: Check 'a'
  → Found! isEnd = true
  → Return "a" immediately! ✓

We DON'T continue to check "aa" or "aaa"!
Why? We want the SHORTEST root!

This is the beauty of Trie:
  - First complete word found = shortest prefix
  - No need to search further
  - Natural shortest-first property! 🎯

Result: "aaaaa" → "a"

🧠 The AHA Moment - Why Trie Wins

Understanding the Search Operation:

KEY INSIGHT: Trie search for PREFIX is different from full word search!

FULL WORD SEARCH (Problems 161-162):
  - Traverse entire word
  - Check isEndOfWord at END
  - Need exact match

  Example: Search "cat" in dictionary
    root → c → a → t → check isEnd

PREFIX SEARCH (This Problem):
  - Traverse word character by character
  - Check isEndOfWord at EACH STEP
  - Stop at FIRST match!

  Example: Search "cattle" for prefix
    root → c → check isEnd? NO, continue
         → a → check isEnd? NO, continue
         → t → check isEnd? YES, STOP! ✓

  Found prefix "cat", don't need "tle"!

This is the CRITICAL difference! 🔑

Visual Comparison - Prefix vs Full Word:

Dictionary: ["cat", "category"]

Trie Structure:
                root
                 |
                 c
                 |
                 a
                 |
                [t] ← Root "cat" ends here
                 |
                 e
                 |
                 g
                 |
                 o
                 |
                 r
                 |
                [y] ← Root "category" ends here

Search "cattle":
  Step 1: c → found, isEnd? NO
  Step 2: a → found, isEnd? NO
  Step 3: t → found, isEnd? YES! ✓

  STOP HERE! Return "cat"

We found the shortest root automatically!
Don't need to check remaining "tle"!

Search "category":
  All steps match, isEnd at 'y'
  Return "category" (exact match)

Search "catalog":
  c → a → t → isEnd? YES!
  Return "cat" (shortest root)
  Don't check "alog"!

The Trie NATURALLY gives us shortest prefix! 🎯

The Algorithm Flow:

PHASE 1: Build Trie
  For each root in dictionary:
    Insert into Trie
    Mark end of root

  Time: O(n * k) where n = roots, k = avg length
  Done ONCE! ✓

PHASE 2: Process Sentence
  For each word in sentence:
    Search in Trie for shortest prefix:
      Traverse character by character
      If isEndOfWord found → STOP, return this prefix
      If no match → return original word
    Append result to output

  Time: O(m * l) where m = words, l = avg length

Total: O(n * k + m * l) - Linear in input size! 🚀

🎯 Solution Approaches

Approach 1: Brute Force

Idea: For each word, try all roots and find shortest match.

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        String[] words = sentence.split(" ");
        StringBuilder result = new StringBuilder();

        for (String word : words) {
            String shortest = word;  // Default to original

            // Try each root
            for (String root : dictionary) {
                // Does word start with this root?
                if (word.startsWith(root)) {
                    // Keep shortest root
                    if (root.length() < shortest.length()) {
                        shortest = root;
                    }
                }
            }

            if (result.length() > 0) {
                result.append(" ");
            }
            result.append(shortest);
        }

        return result.toString();
    }
}

Analysis: - Time Complexity: O(m * n * k) where m = words, n = roots, k = avg root length - Space Complexity: O(1) excluding output - Pros: Simple, no extra data structure - Cons: Very slow for large inputs, repeated comparisons

Approach 2: HashSet Optimization

Idea: Use HashSet for O(1) root lookup, check all prefixes.

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        Set<String> rootSet = new HashSet<>(dictionary);
        String[] words = sentence.split(" ");
        StringBuilder result = new StringBuilder();

        for (String word : words) {
            String replacement = word;

            // Try all possible prefixes from shortest
            for (int i = 1; i <= word.length(); i++) {
                String prefix = word.substring(0, i);
                if (rootSet.contains(prefix)) {
                    replacement = prefix;
                    break;  // Found shortest!
                }
            }

            if (result.length() > 0) {
                result.append(" ");
            }
            result.append(replacement);
        }

        return result.toString();
    }
}

Analysis: - Time Complexity: O(m * l²) where l = avg word length (substring creation) - Space Complexity: O(n * k) for HashSet - Pros: Better than brute force, finds shortest automatically - Cons: Creates many temporary strings, doesn't leverage prefix structure

Approach 3: Trie (Optimal Solution) ⭐

Idea: Build Trie with roots, search for shortest prefix per word.

class Solution {
    // Trie Node - same structure as before!
    private class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEndOfWord = false;
    }

    private TrieNode root = new TrieNode();

    public String replaceWords(List<String> dictionary, String sentence) {
        // Step 1: Build Trie with all roots
        for (String root : dictionary) {
            insert(root);
        }

        // Step 2: Process each word in sentence
        String[] words = sentence.split(" ");
        StringBuilder result = new StringBuilder();

        for (String word : words) {
            if (result.length() > 0) {
                result.append(" ");
            }
            // Find shortest root for this word
            result.append(findShortestRoot(word));
        }

        return result.toString();
    }

    // Standard Trie insert - same as before!
    private void insert(String word) {
        TrieNode node = root;

        for (char ch : word.toCharArray()) {
            int index = ch - 'a';

            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }

            node = node.children[index];
        }

        node.isEndOfWord = true;
    }

    // NEW: Find shortest root (prefix) for a word
    private String findShortestRoot(String word) {
        TrieNode node = root;
        StringBuilder prefix = new StringBuilder();

        for (char ch : word.toCharArray()) {
            int index = ch - 'a';

            // Character not in Trie? No root exists!
            if (node.children[index] == null) {
                return word;  // Return original word
            }

            // Move to next character
            prefix.append(ch);
            node = node.children[index];

            // Found a complete root? STOP HERE!
            if (node.isEndOfWord) {
                return prefix.toString();  // Return shortest root
            }
        }

        // Traversed entire word, no root found
        return word;
    }
}

Analysis: - Time Complexity: O(n * k + m * l) where n = roots, k = avg root length, m = words, l = avg word length - Space Complexity: O(n * k) for Trie structure - Pros: Optimal time, natural prefix matching, scalable - Cons: More complex implementation, extra space

📝 Detailed Dry Run

Dictionary: ["cat", "bat", "rat"]
Sentence: "the cattle was rattled by the battery"

PHASE 1: Build Trie

═══════════════════════════════════════════════
BUILD TRIE - INSERT ALL ROOTS
═══════════════════════════════════════════════

Insert "cat":
  root
   |
   c
   |
   a
   |
  [t] ← isEndOfWord = true

Insert "bat":
  root
  / \
 b   c
 |   |
 a   a
 |   |
[t] [t]

Insert "rat":
  root
 /|\\
b c r
| | |
a a a
| | |
[t][t][t]

Final Trie built! ✓
═══════════════════════════════════════════════

PHASE 2: Process Each Word

═══════════════════════════════════════════════
WORD 1: "the"
═══════════════════════════════════════════════

findShortestRoot("the"):

  Start: node = root, prefix = ""

  Character 't':
    index = 't' - 'a' = 19
    node.children[19] exists? NO! ✗

  Return "the" (no root found)

Result: "the"
═══════════════════════════════════════════════

═══════════════════════════════════════════════
WORD 2: "cattle"
═══════════════════════════════════════════════

findShortestRoot("cattle"):

  Start: node = root, prefix = ""

  Character 'c':
    index = 'c' - 'a' = 2
    node.children[2] exists? YES ✓
    prefix = "c"
    node = node.children[2]
    node.isEndOfWord? NO

  Character 'a':
    index = 'a' - 'a' = 0
    node.children[0] exists? YES ✓
    prefix = "ca"
    node = node.children[0]
    node.isEndOfWord? NO

  Character 't':
    index = 't' - 'a' = 19
    node.children[19] exists? YES ✓
    prefix = "cat"
    node = node.children[19]
    node.isEndOfWord? YES! ✓✓

    STOP! Return "cat"

Result: "cat" (replaced "cattle" with root)
═══════════════════════════════════════════════

═══════════════════════════════════════════════
WORD 3: "was"
═══════════════════════════════════════════════

findShortestRoot("was"):

  Start: node = root, prefix = ""

  Character 'w':
    index = 'w' - 'a' = 22
    node.children[22] exists? NO! ✗

  Return "was" (no root found)

Result: "was"
═══════════════════════════════════════════════

═══════════════════════════════════════════════
WORD 4: "rattled"
═══════════════════════════════════════════════

findShortestRoot("rattled"):

  Start: node = root, prefix = ""

  Character 'r':
    index = 'r' - 'a' = 17
    node.children[17] exists? YES ✓
    prefix = "r"
    node = node.children[17]
    node.isEndOfWord? NO

  Character 'a':
    index = 'a' - 'a' = 0
    node.children[0] exists? YES ✓
    prefix = "ra"
    node = node.children[0]
    node.isEndOfWord? NO

  Character 't':
    index = 't' - 'a' = 19
    node.children[19] exists? YES ✓
    prefix = "rat"
    node = node.children[19]
    node.isEndOfWord? YES! ✓✓

    STOP! Return "rat"

Result: "rat" (replaced "rattled" with root)
═══════════════════════════════════════════════

═══════════════════════════════════════════════
WORD 5: "by"
═══════════════════════════════════════════════

findShortestRoot("by"):

  Start: node = root, prefix = ""

  Character 'b':
    index = 'b' - 'a' = 1
    node.children[1] exists? YES ✓
    prefix = "b"
    node = node.children[1]
    node.isEndOfWord? NO

  Character 'y':
    index = 'y' - 'a' = 24
    node.children[24] exists? NO! ✗

  Return "by" (no root found)

Result: "by"
═══════════════════════════════════════════════

═══════════════════════════════════════════════
WORD 6: "the"
═══════════════════════════════════════════════

(Same as Word 1)

Result: "the"
═══════════════════════════════════════════════

═══════════════════════════════════════════════
WORD 7: "battery"
═══════════════════════════════════════════════

findShortestRoot("battery"):

  Start: node = root, prefix = ""

  Character 'b':
    index = 'b' - 'a' = 1
    node.children[1] exists? YES ✓
    prefix = "b"
    node = node.children[1]
    node.isEndOfWord? NO

  Character 'a':
    index = 'a' - 'a' = 0
    node.children[0] exists? YES ✓
    prefix = "ba"
    node = node.children[0]
    node.isEndOfWord? NO

  Character 't':
    index = 't' - 'a' = 19
    node.children[19] exists? YES ✓
    prefix = "bat"
    node = node.children[19]
    node.isEndOfWord? YES! ✓✓

    STOP! Return "bat"

Result: "bat" (replaced "battery" with root)
═══════════════════════════════════════════════

FINAL SENTENCE:
  Words: ["the", "cat", "was", "rat", "by", "the", "bat"]
  Joined: "the cat was rat by the bat" ✓

═══════════════════════════════════════════════

Key Observations:

1. STOP at first isEndOfWord
   - "cattle" → stopped at "cat" (didn't check "tle")
   - "rattled" → stopped at "rat" (didn't check "tled")
   - "battery" → stopped at "bat" (didn't check "tery")

2. No root found → keep original
   - "the", "was", "by" unchanged

3. Efficient search
   - Each word searched in O(word length)
   - Not O(dictionary size)!

4. StringBuilder for result
   - Efficient string building
   - Add space between words

5. One-time Trie build
   - O(total root characters)
   - Reused for all words! ✓

📊 Complexity Analysis

Approach 3: Trie Solution (Optimal)

Time Complexity:

n = number of roots in dictionary
k = average length of roots
m = number of words in sentence
l = average length of words

Build Trie:
  - Insert n roots
  - Each root: O(k)
  - Total: O(n * k)

Process Sentence:
  - Split sentence: O(sentence length)
  - Search m words
  - Each word: O(l) in worst case
  - Total: O(m * l)

Overall: O(n * k + m * l) ✨

Compare with brute force:
  - For each word, check all roots
  - O(m * n * min(k, l))

Trie is much better when n is large! 🚀

Space Complexity:

Trie space:
  - Worst case: all roots have unique characters
  - O(n * k) for n roots of length k
  - Best case: roots share prefixes
  - Still O(n * k) in worst case

Result string:
  - O(sentence length)
  - Same as input size

Overall: O(n * k + sentence length) 📦

The Trie space is justified by:
  - Faster search
  - Natural prefix sharing
  - Automatic shortest-first property

🎯 Pattern Recognition

The Three Trie Search Patterns:

┌──────────────────────────────────────────────────────┐
│         PATTERN 1: EXACT WORD SEARCH                 │
├──────────────────────────────────────────────────────┤
│ Use Case: Dictionary lookup                          │
│ Problems: 161 (Implement Trie)                       │
│                                                       │
│ Algorithm:                                            │
│   1. Traverse entire word                            │
│   2. Check isEndOfWord at END                        │
│   3. Return true/false                               │
│                                                       │
│ Example: Search "cat"                                │
│   root → c → a → t (check isEnd here only)           │
└──────────────────────────────────────────────────────┘

┌──────────────────────────────────────────────────────┐
│         PATTERN 2: PREFIX SEARCH (SHORTEST)          │
├──────────────────────────────────────────────────────┤
│ Use Case: Root replacement, autocomplete             │
│ Problems: 164 (Replace Words)                        │
│                                                       │
│ Algorithm:                                            │
│   1. Traverse character by character                 │
│   2. Check isEndOfWord at EACH STEP                  │
│   3. STOP at first match (shortest)                  │
│                                                       │
│ Example: Search "cattle" for prefix                  │
│   root → c (check) → a (check) → t (FOUND! Stop)     │
└──────────────────────────────────────────────────────┘

┌──────────────────────────────────────────────────────┐
│         PATTERN 3: WILDCARD SEARCH                   │
├──────────────────────────────────────────────────────┤
│ Use Case: Pattern matching with wildcards            │
│ Problems: 162 (Design Add and Search Words)          │
│                                                       │
│ Algorithm:                                            │
│   1. Traverse with backtracking                      │
│   2. Handle '.' by trying all children               │
│   3. Check isEndOfWord at END                        │
│                                                       │
│ Example: Search "c.t"                                │
│   root → c → try all 26 children → t (check end)     │
└──────────────────────────────────────────────────────┘

KEY INSIGHT:
  Same Trie structure, different search strategies! 🔑

1. Implement Trie (208) - Basic structure
   Pattern: Exact word search

2. Design Add and Search Words (211)
   Pattern: Wildcard search

3. Replace Words (648) - This problem!
   Pattern: Prefix search (shortest)

4. Word Search II (212) - Board + Trie
   Pattern: Backtracking + Trie

5. Longest Word in Dictionary (720)
   Pattern: Prefix building

6. Search Suggestions System (1268)
   Pattern: Prefix search (all matches)

All use the SAME Trie structure! 🎯

🔍 Common Mistakes

❌ Mistake 1: Checking isEnd only at word end

// WRONG!
private String findShortestRoot(String word) {
    TrieNode node = root;
    StringBuilder prefix = new StringBuilder();

    for (char ch : word.toCharArray()) {
        int index = ch - 'a';
        if (node.children[index] == null) return word;
        prefix.append(ch);
        node = node.children[index];
    }

    // Only checking at end - TOO LATE!
    if (node.isEndOfWord) {
        return prefix.toString();
    }
    return word;
}

// CORRECT! ✓
private String findShortestRoot(String word) {
    TrieNode node = root;
    StringBuilder prefix = new StringBuilder();

    for (char ch : word.toCharArray()) {
        int index = ch - 'a';
        if (node.children[index] == null) return word;

        prefix.append(ch);
        node = node.children[index];

        // Check at EACH step!
        if (node.isEndOfWord) {
            return prefix.toString();  // Stop immediately!
        }
    }

    return word;
}

❌ Mistake 2: Not building result efficiently

// WRONG! - String concatenation is O(n²)
String result = "";
for (String word : words) {
    result += findRoot(word) + " ";  // SLOW!
}

// CORRECT! ✓ - StringBuilder is O(n)
StringBuilder result = new StringBuilder();
for (String word : words) {
    if (result.length() > 0) {
        result.append(" ");
    }
    result.append(findRoot(word));
}

❌ Mistake 3: Forgetting space handling

// WRONG! - Extra space at end
for (String word : words) {
    result.append(findRoot(word));
    result.append(" ");  // Adds space after last word!
}

// CORRECT! ✓ - Add space BETWEEN words only
for (String word : words) {
    if (result.length() > 0) {
        result.append(" ");
    }
    result.append(findRoot(word));
}

❌ Mistake 4: Not handling "no root found" case

// WRONG! - What if no root found?
private String findShortestRoot(String word) {
    TrieNode node = root;
    StringBuilder prefix = new StringBuilder();

    for (char ch : word.toCharArray()) {
        int index = ch - 'a';
        if (node.children[index] == null) {
            // Missing return statement!
        }
        prefix.append(ch);
        node = node.children[index];
        if (node.isEndOfWord) {
            return prefix.toString();
        }
    }
    // Missing default case!
}

// CORRECT! ✓ - Return original word
private String findShortestRoot(String word) {
    TrieNode node = root;
    StringBuilder prefix = new StringBuilder();

    for (char ch : word.toCharArray()) {
        int index = ch - 'a';
        if (node.children[index] == null) {
            return word;  // No root found
        }
        prefix.append(ch);
        node = node.children[index];
        if (node.isEndOfWord) {
            return prefix.toString();
        }
    }

    return word;  // Default case
}

📝 Quick Revision Notes

🎯 Core Concept

Replace Words uses Trie for prefix matching. Build Trie with all roots (O(nk)), then for each word find shortest matching prefix (O(ml)). Key difference from standard Trie: check isEndOfWord at EACH step, not just at end. STOP at first match = shortest root automatically! Better than brute force O(mnk).

⚡ Quick Implementation

import java.util.Arrays;
import java.util.List;

class TrieNode {
  TrieNode[] children;
  boolean isEnd;

  public TrieNode() {
    // Just space allocated. All are NULLs.
    // For example, this.children[0] = null, this.children[1] = null and so on till this.children[25] = null
    // Why null? We will initialize with new TrieNode() only when character comes. Why unncessary space before char comes?
    // Check insert method. Only when character comes, we go and initialize that element in the array.
    // For binary numbers, you do need 26 (as its just 0 or 1). Also, isEnd is not required. 
    // But lets use the same for all problems to have it generic.
    this.children = new TrieNode[26];
    this.isEnd = false;
  }  
}

public class Solution {
  TrieNode root;

  public String replaceWords(List<String> dictionary, String sentence) {
    root = new TrieNode();

    // Build Trie with dictionary list.
    for(String word : dictionary) {
      insert(word);
    }

    // Build the result now.
    StringBuilder sb = new StringBuilder();
    for(String word : sentence.split(" ")) {
      String match = checkRootWord(word);
      sb.append(match).append(" ");
    }

    return sb.toString().trim();
  }

  private String checkRootWord(String word) {
    TrieNode curr = root;
    StringBuilder sb = new StringBuilder();

    for(char ch : word.toCharArray()) {
      int index = ch - 'a';

      if(curr.children[index] == null) {
        return word; // char not found. Immediately return
      }

      curr = curr.children[index];

      // if matches, append the existing character from Trie
      sb.append(ch);

      // If root is found at any character, return immediately.
      if(curr.isEnd) {
        return sb.toString();
      }      
    }

    return word;
  }

  private void insert(String word) {
    TrieNode curr = root;
    for(char ch : word.toCharArray()) {
      int index = ch - 'a';

      if(curr.children[index] == null) {
        curr.children[index] = new TrieNode();
      }

      curr = curr.children[index];
    }

    curr.isEnd = true;
  }

  public static void main(String[] args) {
        Solution s = new Solution();
    System.out.println(s.replaceWords(Arrays.asList(new String[] {"cat","bat","rat"}), "the cattle was rattled by the battery")); // "the cat was rat by the bat"
    System.out.println(s.replaceWords(Arrays.asList(new String[] {"a","b","c"}), "aadsfasf absbs bbab cadsfafs")); // "a a b c"
    }
}

🔑 Key Insights

Prefix vs Full Word Search:

Full Word (161): Check isEnd at LAST character
  "cat" → c → a → t (check here only)

Prefix (164): Check isEnd at EVERY character
  "cattle" → c (check) → a (check) → t (FOUND!)

STOP at first match = shortest automatically! 🎯

Why Trie Wins:

Without Trie:
  For each word: try all roots
  Time: O(m * n * k)

With Trie:
  For each word: navigate Trie once
  Time: O(m * l)

Trie eliminates redundant comparisons! 🚀

The Search Pattern:

for (char ch : word.toCharArray()) {
    // 1. Path exists?
    if (node.children[idx] == null) return word;

    // 2. Move forward
    prefix.append(ch);
    node = node.children[idx];

    // 3. Complete root? STOP!
    if (node.isEndOfWord) return prefix.toString();
}

This is the magic formula! ✨

🎪 Memory Hooks

"Check isEnd at every step, not just the end!"
"First match = shortest match!"
"No path? Return original!"
"StringBuilder for efficiency!" 🔥

⚠️ Don't Forget

Check isEndOfWord at EACH character (not just end!)
STOP at first complete root (shortest!)
Handle "no root found" case (return original)
Use StringBuilder for result building
Add space BETWEEN words only (not at end)
Insert happens ONCE (build phase)
Search happens for EVERY word (query phase)

🎉 Congratulations!

You've mastered Trie Prefix Matching!

What You Learned:

✅ Prefix search - different from exact word search
✅ Check at each step - not just at end
✅ Shortest-first property - automatic with Trie
✅ O(nk + ml) complexity - optimal solution
✅ StringBuilder efficiency - for string building
✅ Pattern recognition - three Trie search types

The Three Trie Search Patterns:

Problem 161 (Implement Trie):
  Pattern: EXACT WORD SEARCH
  Check: isEndOfWord at END only

Problem 162 (Add and Search):
  Pattern: WILDCARD SEARCH
  Check: Backtracking with '.'

Problem 164 (Replace Words):
  Pattern: PREFIX SEARCH
  Check: isEndOfWord at EACH STEP

Same structure, different strategies! 🎯

Interview Mastery:

Interviewer: "Replace derivatives with roots"

Your response:
  "Classic Trie prefix matching!

   Approach:
   1. Build Trie with all roots
   2. For each word, find shortest matching prefix
   3. Check isEndOfWord at EACH step (not just end)
   4. STOP at first match

   Why Trie:
   - Natural prefix structure
   - Automatic shortest-first
   - O(n*k + m*l) vs O(m*n*k) brute force
   - Much faster for large dictionaries

   Key insight:
   - Different from exact word search
   - Must check isEnd at every character
   - First complete root = shortest root

   Implementation:
   - Standard Trie structure
   - Modified search with early stop
   - StringBuilder for efficiency

   Complexity:
   - Time: O(n*k + m*l)
   - Space: O(n*k) for Trie

   Much better than trying all roots per word!"

Shows complete understanding! 💯

Your Trie Journey So Far:

Problem 161: Basic Trie ✓
  - Insert, Search, StartsWith
  - Foundation concepts

Problem 162: Wildcard Trie ✓
  - Backtracking with '.'
  - Recursive search

Problem 163: Binary Trie ✓
  - 2 children (not 26)
  - XOR optimization

Problem 164: Prefix Matching Trie ✓
  - Check at each step
  - Shortest-first property

You're becoming a Trie expert! 🏆✨

Keep this momentum going! You're mastering Trie patterns! 🚀

164. Replace Words

Problem Statement

🌳 Visual Understanding - The Complete Picture

The Problem We're Solving:

Why Trie is Perfect:

The Trie Magic - Visual Structure:

Complete Visual Walkthrough:

The "Shortest Root" Property:

🧠 The AHA Moment - Why Trie Wins

Understanding the Search Operation:

Visual Comparison - Prefix vs Full Word:

The Algorithm Flow:

🎯 Solution Approaches

Approach 1: Brute Force

Approach 2: HashSet Optimization

Approach 3: Trie (Optimal Solution) ⭐

📝 Detailed Dry Run

PHASE 1: Build Trie

PHASE 2: Process Each Word

Key Observations:

📊 Complexity Analysis

Approach 3: Trie Solution (Optimal)

🎯 Pattern Recognition

The Three Trie Search Patterns:

Related Problems:

🔍 Common Mistakes

❌ Mistake 1: Checking isEnd only at word end

❌ Mistake 2: Not building result efficiently

❌ Mistake 3: Forgetting space handling

❌ Mistake 4: Not handling "no root found" case

📝 Quick Revision Notes

🎯 Core Concept

⚡ Quick Implementation

🔑 Key Insights

🎪 Memory Hooks

⚠️ Don't Forget

🎉 Congratulations!

What You Learned:

The Three Trie Search Patterns:

Interview Mastery:

Your Trie Journey So Far: