Replace Words
Solve this Problemsentence, replace every word in the sentence that has one of the roots as a prefix with that root — the shortest one, if more than one root matches. Words with no matching root pass through unchanged.
Checking a word against every root one at a time works, but it repeats the same character comparisons across similar words. Building a trie of the roots instead means walking a word down it costs only as many steps as the word has characters before either falling off (no root matches) or landing on a node marking a complete root — and since that walk naturally proceeds shortest-prefix-first, the first root it finds is guaranteed to be the shortest one, with no length comparison needed at all.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ roots.length ≤ 1000 - ◆
1 ≤ roots[i].length ≤ 20 - ◆
1 ≤ sentence.length ≤ 1000 - ◆
roots[i] and every word in sentence consist of lowercase English letters - ◆
sentence is a single space-separated string with no leading, trailing, or doubled spaces
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Check Every Root Against Every Word
BruteSplit the sentence into words. For each word, scan every root in the list, keeping track of whichever matching root turns out shortest. With w words, r roots, and up to L characters compared per check, that's a full re-scan of every root for every single word — no sharing of work between similar words at all.
O(w · r · L)O(sentence.length)1class Solution {
2 public String replaceWords(String[] roots, String sentence) {
3 String[] words = sentence.split(" ");
4 StringBuilder result = new StringBuilder();
5 for (int w = 0; w < words.length; w++) {
6 String word = words[w];
7 String shortestRoot = null;
8 for (String root : roots) {
9 if (word.startsWith(root)) {
10 if (shortestRoot == null || root.length() < shortestRoot.length()) {
11 shortestRoot = root;
12 }
13 }
14 }
15 if (w > 0) result.append(" ");
16 result.append(shortestRoot != null ? shortestRoot : word);
17 }
18 return result.toString();
19 }
20}Optimal — Trie of Roots, Walk Each Word Once
OptimalInsert every root into a trie up front — that's a one-time O(R) cost, where R is the total characters across all roots. Then for each word in the sentence, walk it down the trie one character at a time. The instant that walk passes a node marked as the end of some root, stop right there — since roots are walked shortest-reachable-first by construction, the first isEnd node hit is automatically the shortest matching root, no comparison against the others needed.
O(R + w · L)O(R)1class Solution {
2 static class TrieNode {
3 TrieNode[] children = new TrieNode[26];
4 boolean isEnd = false;
5 }
6
7 public String replaceWords(String[] roots, String sentence) {
8 TrieNode root = new TrieNode();
9 for (String r : roots) {
10 TrieNode node = root;
11 for (char c : r.toCharArray()) {
12 int idx = c - 'a';
13 if (node.children[idx] == null) {
14 node.children[idx] = new TrieNode();
15 }
16 node = node.children[idx];
17 }
18 node.isEnd = true;
19 }
20
21 String[] words = sentence.split(" ");
22 StringBuilder result = new StringBuilder();
23 for (int w = 0; w < words.length; w++) {
24 String word = words[w];
25 TrieNode node = root;
26 int cut = -1;
27 for (int i = 0; i < word.length(); i++) {
28 int idx = word.charAt(i) - 'a';
29 if (node.children[idx] == null) break;
30 node = node.children[idx];
31 if (node.isEnd) {
32 cut = i;
33 break;
34 }
35 }
36 if (w > 0) result.append(" ");
37 result.append(cut == -1 ? word : word.substring(0, cut + 1));
38 }
39 return result.toString();
40 }
41}