Replace Words

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”

Constraints:

• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 100
• dictionary[i] consists of only lower-case letters.
• 1 <= sentence.length <= 106
• 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]
• Every two consecutive words in sentence will be separated by exactly one space.
• sentence does not have leading or trailing spaces.

Approach: Trie Lookup of the Shortest Root

Algorithm

1. Build a trie from the dictionary roots, marking the end of each root
2. Split the sentence into words
3. For each word, walk the trie character by character: if a root end is reached, use the prefix as the replacement; if the path breaks, keep the original word

Time & Space Complexity

• Time Complexity: O(N * L) - N words of length L; trie construction and per-word traversal are linear
• Space Complexity: O(sum of dictionary root lengths) - the trie nodes

Java Implementation

import java.util.List;

public class ReplaceWords {

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

    /**
     * Replace derivatives in the sentence with their shortest root.
     * @param dictionary List of root words
     * @param sentence Input sentence
     * @return Sentence with roots substituted
     */
    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = new TrieNode();
        for (String word : dictionary) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int index = c - 'a';
                if (node.children[index] == null) {
                    node.children[index] = new TrieNode();
                }
                node = node.children[index];
            }
            node.isEnd = true;
        }

        StringBuilder result = new StringBuilder();
        String[] words = sentence.split(" ");

        for (int i = 0; i < words.length; i++) {
            if (i > 0) {
                result.append(' ');
            }

            TrieNode node = root;
            StringBuilder prefix = new StringBuilder();
            boolean replaced = false;

            for (char c : words[i].toCharArray()) {
                int index = c - 'a';
                if (node == null || node.children[index] == null) {
                    break;
                }
                node = node.children[index];
                prefix.append(c);
                if (node.isEnd) {
                    result.append(prefix);
                    replaced = true;
                    break;
                }
            }

            if (!replaced) {
                result.append(words[i]);
            }
        }

        return result.toString();
    }

    // Test method
    public static void main(String[] args) {
        ReplaceWords rw = new ReplaceWords();
        List<String> dictionary = List.of("cat", "bat", "rat");
        System.out.println("Input: dictionary = [\"cat\",\"bat\",\"rat\"], sentence = \"the cattle was rattled by the battery\"");
        System.out.println("Output: \"" + rw.replaceWords(dictionary, "the cattle was rattled by the battery") + "\"");
        // Expected: "the cat was rat by the bat"
    }
}

Example Walkthrough

With roots [“cat”,“bat”,“rat”] and sentence “the cattle was rattled by the battery”:

1. “the”: no path in the trie at ‘t’ -> kept as “the”
2. “cattle”: trie path c-a-t reaches an end -> replaced with “cat”
3. “rattled”: r-a-t is a root end -> “rat”
4. “battery”: b-a-t is a root end -> “bat”

Final output: "the cat was rat by the bat".

Key Points

1. First Match Wins: The trie stops at the first isEnd reached, which is naturally the shortest root
2. Prefix Traversal: Walking the word through the trie finds any root prefix in O(L)
3. Root Length Priority: The shortest matching root is found automatically by the top-down walk
4. No Match Handling: When the trie path breaks, the original word is preserved
5. Alternative: A set of roots plus substring checks would be O(L²) per word