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 successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".

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

Return the sentence after the replacement.

Examples

Example 1:

Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
Explanation: 
- "cattle" can be replaced by "cat" (shortest root)
- "rattled" can be replaced by "rat" (shortest root)
- "battery" can be replaced by "bat" (shortest root)

Example 2:

Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"
Explanation: 
- "aadsfasf" can be replaced by "a" (shortest root)
- "absbs" can be replaced by "a" (shortest root)
- "bbab" can be replaced by "b" (shortest root)
- "cadsfafs" can be replaced by "c" (shortest root)

Constraints

  • 1 <= dictionary.length <= 1000
  • 1 <= dictionary[i].length <= 100
  • 1 <= sentence.length <= 10^6
  • sentence consists of only lower-case 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]
  • Each word in sentence consists of only lower-case letters.

Thinking Process

  1. Simple implementation: Easy to understand and implement
  2. Efficient traversal: Character-by-character matching
  • Identify the pattern from constraints (sorted? graph? optimal substructure?).
  • Write brute force first mentally, then optimize the bottleneck.
  • Verify edge cases: empty input, single element, duplicates.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Brute force (this problem) Often O(n^2) or O(2^n) O(n) Baseline; clarifies the optimization target
Sort + scan O(n log n) O(1) Pairs, intervals, greedy ordering
Hash map / set O(n) O(n) Frequency, membership, two-sum style
Single-pass linear O(n) O(1) Two pointers, sliding window, Kadane

Solution

Time Complexity: O(n * m) where n is number of words, m is average word length
Space Complexity: O(d) where d is dictionary size

Use a hash set to store dictionary roots and check prefixes for each word.

class Solution {
    private String shortestRoot(Set<String> roots, String word) {
        for (int i = 1; i <= word.length(); i++) {
            String prefix = word.substring(0, i);
            if (roots.contains(prefix)) {
                return prefix;
            }
        }
        return word;
    }

    public String replaceWords(List<String> dictionary, String sentence) {
        Set<String> roots = new HashSet<>(dictionary);
        StringBuilder result = new StringBuilder();
        for (String word : sentence.split(" ")) {
            if (result.length() > 0) {
                result.append(' ');
            }
            result.append(shortestRoot(roots, word));
        }
        return result.toString();
    }
}

Solution Explanation

Approach: Brute force (this problem)

Key idea: 1. Simple implementation: Easy to understand and implement

How the code works:

  1. Simple implementation: Easy to understand and implement
  2. Efficient traversal: Character-by-character matching
    • Identify the pattern from constraints (sorted? graph? optimal substructure?).
    • Write brute force first mentally, then optimize the bottleneck.
    • Verify edge cases: empty input, single element, duplicates.

Walkthrough — input dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery", expected output "the cat was rat by the bat":

  • “cattle” can be replaced by “cat” (shortest root)
  • “rattled” can be replaced by “rat” (shortest root)
  • “battery” can be replaced by “bat” (shortest root)
Approach Time Complexity Space Complexity
Hash Set O(n * m) O(d)
Trie O(n * m) O(d * k)

Where:

  • n = number of words in sentence
  • m = average word length
  • d = dictionary size
  • k = average root length

    How the Algorithms Work

Solution 1: Hash Set Approach

Key Insight: For each word, check all possible prefixes to find the shortest root.

Steps:

  1. Store dictionary in hash set for O(1) lookup
  2. For each word, check prefixes of increasing length
  3. Return shortest root found, or original word if none found
  4. Build new sentence with replaced words

Solution 2: Trie Approach

Key Insight: Use trie to efficiently traverse and find shortest root prefix.

Steps:

  1. Build trie from dictionary roots
  2. For each word, traverse trie character by character
  3. Return shortest root when reaching end node, or original word
  4. Build new sentence with replaced words

Step-by-Step Examples

Solution 1 Example: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled"

Word Check Prefixes Found Root Result
“the” “t”, “th”, “the” None “the”
“cattle” “c”, “ca”, “cat” “cat” “cat”
“was” “w”, “wa”, “was” None “was”
“rattled” “r”, “ra”, “rat” “rat” “rat”

Final result: "the cat was rat"

Solution 2 Example: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled"

Trie Structure:

root
├── c → a → t (end)
├── b → a → t (end)
└── r → a → t (end)
Word Trie Traversal Found Root Result
“the” t → h → e (not found) None “the”
“cattle” c → a → t (end) “cat” “cat”
“was” w (not found) None “was”
“rattled” r → a → t (end) “rat” “rat”

Final result: "the cat was rat"

Algorithm Breakdown

Solution 2: Trie

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
}

class Trie {
    private final TrieNode root = new TrieNode();

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    String shortestRoot(String word) {
        TrieNode node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                return word;
            }
            node = node.children[idx];
            if (node.isEnd) {
                return word.substring(0, i + 1);
            }
        }
        return word;
    }
}

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        Trie trie = new Trie();
        for (String root : dictionary) {
            trie.insert(root);
        }
        StringBuilder result = new StringBuilder();
        for (String word : sentence.split(" ")) {
            if (result.length() > 0) {
                result.append(' ');
            }
            result.append(trie.shortestRoot(word));
        }
        return result.toString();
    }
}

Process:

  1. Check prefixes of increasing length
  2. Return first match (shortest root)
  3. Return original word if no match found

Solution 2: Trie

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        StringBuilder result = new StringBuilder();
        for (String word : sentence.split(" ")) {
            if (result.length() > 0) {
                result.append(' ');
            }
            String shortest = word;
            for (String root : dictionary) {
                if (word.startsWith(root) && root.length() < shortest.length()) {
                    shortest = root;
                }
            }
            result.append(shortest);
        }
        return result.toString();
    }
}

Process:

  1. Traverse trie character by character
  2. Return prefix when reaching end node
  3. Return original word if path doesn’t exist

Complexity

| Approach | Time Complexity | Space Complexity | |———-|—————-|——————| | Hash Set | O(n * m) | O(d) | | Trie | O(n * m) | O(d * k) |

Where:

  • n = number of words in sentence
  • m = average word length
  • d = dictionary size
  • k = average root length

Common Mistakes

  1. Single word: dictionary = ["a"], sentence = "a" → "a"
  2. No matches: dictionary = ["cat"], sentence = "dog" → "dog"
  3. Empty dictionary: dictionary = [], sentence = "hello" → "hello"

  4. Single character roots: dictionary = ["a","b"], sentence = "abc" → "a"

  5. Wrong prefix order: Not checking shortest prefixes first
  6. Missing edge cases: Not handling empty dictionary or sentence
  7. String building: Inefficient string concatenation
  8. Trie implementation: Not properly setting end markers

Detailed Example Walkthrough

Solution 1: dictionary = ["a","aa","aaa"], sentence = "a aa aaa"

Hash Set: {"a", "aa", "aaa"}

Word Prefix Check Found Root Result
“a” “a” “a” “a”
“aa” “a” “a” “a”
“aaa” “a” “a” “a”

Final result: "a a a"

Solution 2: dictionary = ["a","aa","aaa"], sentence = "a aa aaa"

Trie Structure:

root
└── a (end)
    └── a (end)
        └── a (end)
Word Trie Traversal Found Root Result
“a” a (end) “a” “a”
“aa” a (end) “a” “a”
“aaa” a (end) “a” “a”

Final result: "a a a"

Why These Solutions Work

Solution 1 (Hash Set):

  1. Correct prefix checking: Checks all prefixes systematically
  2. Shortest first: Returns first match (shortest root)
  3. Efficient lookup: O(1) hash set lookup
  4. Simple logic: Easy to understand and debug

Solution 2 (Trie):

  1. Efficient traversal: Character-by-character matching
  2. Early termination: Stops at first end node
  3. Structured approach: Organized prefix tree
  4. Scalable design: Better for large dictionaries

References

Key Takeaways

Solution 1 (Hash Set):

  1. Simple implementation: Easy to understand and implement
  2. Prefix checking: Check all possible prefixes systematically
  3. Shortest first: Return first match (shortest root)
  4. Space efficient: Only stores dictionary roots

Solution 2 (Trie):

  1. Efficient traversal: Character-by-character matching
  2. Early termination: Stop at first end node found
  3. Structured storage: Organized prefix tree structure
  4. Scalable: Better for large dictionaries