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.
Input: dictionary=["cat","bat","rat"], sentence="the cattle was rattled by the battery" → Output: "the cat was rat by the bat"
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.
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)