#648
Replace Words
Medium Shortest root in a trie
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Given a list of roots and a sentence, replace every word that starts with a root by the shortest such root.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: replace each word with its shortest root from a dictionary.
Why this works: walk the trie along the word; stop at the first node that ends a root.
Example: roots ["cat", "bat", "rat"], sentence "the cattle was rattled"
cattle → cat, rattled → rat"the cat was rat"
✦Hints open one at a time
Insert all roots into a trie.
For each word, walk the trie and stop at the first node that ends a root.
↗Approach
Build the trie. For each word, walk character by character; if a root ends, use the prefix up to there; if the path breaks, keep the word.
</>Solution (Java)
import java.util.*;
class Solution {
private static class Node {
Node[] next = new Node[26];
boolean end;
}
public String replaceWords(List<String> dictionary, String sentence) {
Node root = new Node();
for (String r : dictionary) {
Node cur = root;
for (char c : r.toCharArray()) {
if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new Node();
cur = cur.next[c - 'a'];
}
cur.end = true;
}
StringBuilder sb = new StringBuilder();
for (String w : sentence.split(" ")) {
if (sb.length() > 0) sb.append(' ');
Node cur = root;
int i = 0;
while (i < w.length() && cur.next[w.charAt(i) - 'a'] != null && !cur.end) {
cur = cur.next[w.charAt(i) - 'a'];
i++;
}
sb.append(cur.end ? w.substring(0, i) : w); // shortest root found, or keep the word
}
return sb.toString();
}
}!Common mistake
Checking every root against every word with startsWith — O(words × roots × length).
Complexity
- Time: O(total characters).
- Space: O(total root characters).
Topic: Trie
🎬 Episode 97: video coming soon