Definition
- Trie insertion stores every root word with an end-of-word flag marking each root's terminal node.
- Prefix walk processes each sentence word by following characters through the Trie from the root node.
- Shortest root is found by stopping at the first flagged node encountered during the walk, since flagged nodes appear in increasing prefix length.
- Fallback keeps the original word unchanged if no root prefixes it or the walk falls off the Trie.
- Complexity is O(S + R) where S is the total characters in the sentence and R is the total characters in all roots.
At the National Bank of India, long product names need to be normalized to their shortest official code before feeding into analytics. Rajesh keeps a directory of official short codes in a Trie. Whenever a customer types a long product name, he walks the name letter by letter against the directory and the moment he completes an official code, he stops and swaps the long name for that short code. If no official code matches, the name passes through unchanged.
Understanding the Concepts
What is the Replace Words problem?
You are given a dictionary of root words and a sentence. For every word in the sentence, if a root word from the dictionary is a prefix of that word, replace the word with the shortest such root. If no root is a prefix, keep the word as-is. Return the resulting sentence.
For example, given roots ["cat", "bat", "rat"] and the sentence "the cattle was rattled by the battery", the result is "the cat was rat by the bat".
package com.bank.coding;
import java.util.Arrays;
import java.util.List;
/**
* Replaces words in a sentence with their shortest root prefix
* using a Trie data structure.
*/
public class ReplaceWords {
private static final int ALPHABET_SIZE = 26;
static class TrieNode {
TrieNode[] children = new TrieNode[ALPHABET_SIZE];
boolean isWord = false;
}
private final TrieNode root = new TrieNode();
public void insertRoot(String word) {
TrieNode current = root;
for (char c : word.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
current.children[index] = new TrieNode();
}
current = current.children[index];
}
current.isWord = true;
}
public String findShortestRoot(String word) {
TrieNode current = root;
StringBuilder prefix = new StringBuilder();
for (char c : word.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) {
break; // fell off the Trie
}
current = current.children[index];
prefix.append(c);
if (current.isWord) {
return prefix.toString(); // shortest root found
}
}
return word; // no root matched
}
public String replaceSentence(List<String> roots, String sentence) {
for (String r : roots) {
insertRoot(r);
}
String[] words = sentence.split(" ");
StringBuilder result = new StringBuilder();
for (int i = 0; i < words.length; i++) {
if (i > 0) result.append(" ");
result.append(findShortestRoot(words[i]));
}
return result.toString();
}
public static void main(String[] args) {
ReplaceWords rw = new ReplaceWords();
List<String> roots = Arrays.asList("cat", "bat", "rat");
String sentence = "the cattle was rattled by the battery";
System.out.println(rw.replaceSentence(roots, sentence));
}
}
the cat was rat by the bat
Why does a Trie work here?
A Trie stores all roots in a tree structure where each edge represents a character. When you walk a word through the Trie, you follow one edge per character. The first node you reach that is marked as end-of-word is necessarily the shortest root that prefixes the word, because nodes at smaller depths correspond to shorter strings.
This property eliminates the need to sort roots by length or to check all roots against each word. The Trie walk stops early the moment it finds a match.
// Why the first flagged node is the shortest root:
// Trie for roots ["lo", "loan"]:
// root -> l -> o (isWord=true) -> a -> n (isWord=true)
//
// Walking "loanaccount":
// l -> o -> isWord! Stop here. Return "lo".
// We never reach "loan" because "lo" was hit first.
How does the Trie insertion work?
Each root word is inserted character by character. For each character, if the child node does not exist, create it. After the last character, mark the node's isWord flag as true.
The Trie structure naturally handles overlapping prefixes. If lo and loan are both roots, the o node is flagged and the n node is also flagged. The walk will hit the o node first.
// Trie after inserting ["sav", "savings", "loan", "lo"]
//
// root
// ├── s
// │ └── a
// │ └── v (isWord=true for "sav")
// │ └── i
// │ └── n
// │ └── g
// │ └── s (isWord=true for "savings")
// └── l
// └── o (isWord=true for "lo")
// └── a
// └── n (isWord=true for "loan")
How is this different from a brute-force approach?
The brute-force approach checks every root against every word in the sentence. For each word, it iterates over all roots and checks if the root is a prefix of the word using word.startsWith(root). This is O(W * R * L) where W is the number of words, R is the number of roots, and L is the average root length.
The Trie approach processes each word in O(L) time where L is the word length (or the shortest matching root length), regardless of how many roots exist.
| Aspect | Brute force | Trie approach |
|---|---|---|
| Per-word cost | O(R * L) | O(L) |
| Finds shortest root | Needs sorting or extra logic | Automatic (first flag) |
| Memory | O(1) extra | O(total root characters) |
| Build time | None | O(total root characters) |
| Interview impression | Weak | Strong |
// Brute force: O(W * R * L)
public static String replaceWordsBrute(List<String> roots, String sentence) {
// Sort by length so shortest roots are checked first
roots.sort((a, b) -> a.length() - b.length());
String[] words = sentence.split(" ");
StringBuilder result = new StringBuilder();
for (int i = 0; i < words.length; i++) {
if (i > 0) result.append(" ");
String replacement = words[i];
for (String root : roots) {
if (words[i].startsWith(root)) {
replacement = root;
break; // shortest first due to sorting
}
}
result.append(replacement);
}
return result.toString();
}
What are the edge cases?
The edge cases to consider are:
- Word with no matching root: the word passes through unchanged.
- Word that is itself a root: the word is replaced by itself (no change in value).
- Multiple roots that prefix a word: the shortest one wins because the Trie walk stops at the first flagged node.
- Empty dictionary: every word passes through unchanged.
- Single-character roots: the Trie walk stops at depth 1 for any matching word.
package com.bank.coding;
import java.util.Arrays;
public class ReplaceWordsEdgeCases {
public static void main(String[] args) {
ReplaceWords rw = new ReplaceWords();
// No matching root
System.out.println(rw.replaceSentence(
Arrays.asList("cat"), "the dog ran"));
// Word is itself a root
ReplaceWords rw2 = new ReplaceWords();
System.out.println(rw2.replaceSentence(
Arrays.asList("loan"), "loan processing"));
// Multiple roots, shortest wins
ReplaceWords rw3 = new ReplaceWords();
System.out.println(rw3.replaceSentence(
Arrays.asList("lo", "loan", "loanaccount"), "loanaccount is active"));
// Empty dictionary
ReplaceWords rw4 = new ReplaceWords();
System.out.println(rw4.replaceSentence(
Arrays.asList(), "hello world"));
}
}
the dog ran
loan processing
lo is active
hello world
What are common mistakes?
The most common mistake is returning the longest matching root instead of the shortest. This happens when the Trie walk does not stop at the first flagged node but continues to find longer matches.
// WRONG: finds the longest root, not the shortest
public String findLongestRoot(String word) {
TrieNode current = root;
String longestMatch = null;
StringBuilder prefix = new StringBuilder();
for (char c : word.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) break;
current = current.children[index];
prefix.append(c);
if (current.isWord) {
longestMatch = prefix.toString(); // BUG: keeps going
}
}
return longestMatch != null ? longestMatch : word;
}
// For roots ["lo", "loan"] and word "loanaccount":
// This returns "loan" instead of "lo"
// CORRECT: stop at the first flagged node
public String findShortestRoot(String word) {
TrieNode current = root;
StringBuilder prefix = new StringBuilder();
for (char c : word.toCharArray()) {
int index = c - 'a';
if (current.children[index] == null) break;
current = current.children[index];
prefix.append(c);
if (current.isWord) {
return prefix.toString(); // CORRECT: stop immediately
}
}
return word;
}
Another mistake is not handling the case where the word is shorter than any root. The Trie walk naturally handles this because it stops when the word characters are exhausted.
What is the time and space complexity?
Building the Trie takes O(R) where R is the total number of characters across all roots. Each character is inserted once.
Processing the sentence takes O(S) where S is the total number of characters across all words. Each word is walked through the Trie, and the walk stops at the first flagged node or when the characters run out.
The total time is O(R + S). The space for the Trie is O(R * 26) in the worst case when using fixed-size arrays, or O(R) when using hash maps for children.
// For roots with total length R = 100 and sentence with total length S = 1000:
// Build Trie: O(100)
// Process sentence: O(1000)
// Total: O(1100) = O(R + S)
What about using a HashMap instead of a Trie?
A HashMap approach stores all roots in a set and for each word, checks every possible prefix against the set. This works but requires checking prefixes of increasing length, and it does not naturally stop at the shortest root without explicit logic.
import java.util.HashSet;
import java.util.Set;
public static String replaceWithHashSet(List<String> roots, String sentence) {
Set<String> rootSet = new HashSet<>(roots);
String[] words = sentence.split(" ");
StringBuilder result = new StringBuilder();
for (int i = 0; i < words.length; i++) {
if (i > 0) result.append(" ");
String word = words[i];
String replacement = word;
for (int len = 1; len <= word.length(); len++) {
String prefix = word.substring(0, len);
if (rootSet.contains(prefix)) {
replacement = prefix;
break; // shortest prefix found
}
}
result.append(replacement);
}
return result.toString();
}
The HashSet approach works and is simpler to code, but the Trie avoids creating substring objects and is more efficient for large dictionaries.
What should a senior engineer know?
A senior engineer should know that the Trie is the canonical data structure for prefix-matching problems. Beyond Replace Words, Tries power autocomplete, spell checking, IP routing tables, and DNA sequence matching.
In production, memory optimization matters. A fixed-size array of 26 children per node wastes space when the alphabet is sparse. Using a HashMap for children trades array access speed for memory efficiency. Compressed Tries (radix trees) collapse single-child chains into single edges, further reducing memory.
For the banking domain, normalizing product descriptions to standard codes before analytics is a real-world application where a Trie dictionary provides fast, consistent normalization.
What are common interview follow-up questions?
Interviewers often ask:
- What if you want the longest matching root instead of the shortest? Do not stop at the first flag; track the last flag seen and return it after the walk.
- How would you handle case-insensitive matching? Convert both roots and words to lowercase before insertion and lookup.
- What if roots can overlap with each other? The Trie handles this naturally because overlapping roots share common prefix paths.
- Can you solve this with a regular expression? Yes, by building a regex from the roots, but performance is worse than a Trie for large dictionaries.
Visual Overview
Trie for roots ["cat", "bat", "rat"]:
root
├── c
│ └── a
│ └── t (isWord=true)
├── b
│ └── a
│ └── t (isWord=true)
└── r
└── a
└── t (isWord=true)
Processing: "cattle"
Step 1: c -> child exists, follow
Step 2: a -> child exists, follow
Step 3: t -> child exists, follow
isWord = true! Stop.
Return "cat"
Processing: "the"
Step 1: t -> no child for 't' at root? Actually no 't' root
Wait: 't' has no child from root (roots are cat, bat, rat)
Fell off Trie at step 1.
Return "the" (unchanged)
┌──────────────────────────────────────────┐ │ Replace Words Algorithm │ │ │ │ 1. Build Trie from all root words │ │ 2. For each word in sentence: │ │ ├── Walk the Trie char by char │ │ ├── Hit isWord? → return prefix │ │ ├── No child? → return original word │ │ └── End of word? → return original │ │ 3. Join replaced words with spaces │ └──────────────────────────────────────────┘
Key Takeaway
Replace Words asks you to swap each word of a sentence for the shortest dictionary root that prefixes it, leaving words with no matching root unchanged. The solution inserts every root into a Trie with an end-of-word flag, then processes each sentence word by walking the Trie character by character.
The key insight is that the first flagged node encountered during the walk is automatically the shortest root, because flagged nodes appear at increasing depths along a Trie path. The walk stops the moment it hits a flagged node and returns the prefix built so far. If the walk falls off the Trie because a character has no child, or if it reaches the end of the word without hitting any flagged node, the original word is returned.
At the National Bank of India, Rajesh used this to normalize free-text product descriptions to their shortest official code before feeding analytics. Each word was walked against a Trie of official root codes, and savingsaccount became sav while loanprocessing became lo. Words with no official root passed through unchanged. Stopping at the first flagged node kept normalization fast even over long descriptions.
The Trie is the canonical data structure for prefix-matching problems. Interviewers check that you stop at the first root rather than the longest, that you only replace on a genuine end-of-word match, and that the overall cost is linear in the sentence plus Trie build. This is cleaner and faster than comparing each word against every root.
Remember one sentence: insert roots into a Trie, walk each word until the first end-of-word flag, and that flag gives the shortest root.
---