Replace Words

Given a dictionary of root words, replace every word in a sentence with the shortest root that is a prefix of it. If no root found, leave the word as is.

Example 1

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

Solution Approach

Build a Trie from the dictionary. For each word in the sentence, traverse the Trie until we find a complete root word or exhaust the word.

Insert all roots into Trie.
For each word in sentence: traverse Trie character by character.
If we reach a node marked isEnd (root found): return that root prefix.
If we exhaust the word without finding a root: keep original word.

Java

import java.util.*;

class Solution {
    public String replaceWords(List<String> dictionary, String sentence) {
        TrieNode root = new TrieNode();
        for (String root_ : dictionary) {
            TrieNode node = root;
            for (char c : root_.toCharArray()) {
                if (node.ch[c-'a']==null) node.ch[c-'a'] = new TrieNode();
                node = node.ch[c-'a'];
                if (node.word != null) break;
            }
            node.word = root_;
        }
        String[] words = sentence.split(" ");
        StringBuilder sb = new StringBuilder();
        for (String w : words) {
            TrieNode node = root;
            String replacement = w;
            for (char c : w.toCharArray()) {
                if (node.ch[c-'a']==null || node.word!=null) break;
                node = node.ch[c-'a'];
                if (node.word != null) { replacement = node.word; break; }
            }
            if (sb.length() > 0) sb.append(' ');
            sb.append(replacement);
        }
        return sb.toString();
    }
    static class TrieNode { TrieNode[] ch=new TrieNode[26]; String word; }
}

Time Complexity: O(D*L + S) where D=dictionary size, L=max length, S=sentence length
Space Complexity: O(D*L)