Definition
- Trie insertion – insert all root words into a trie, marking the end of each root with a flag.
- Prefix walk – for each sentence word, traverse the trie character by character from the root node.
- Early stop – the moment you reach a node marked as a root, stop: this is the shortest root that is a prefix of the word.
- No match – if at some character there is no matching child, or you finish the word without hitting a root, keep the original word.
- Linear time – each word costs time proportional to its own length (or the matching root length).
The National Bank of India normalizes long transaction descriptor words down to their shortest registered root code. A trie of root codes lets each descriptor be shortened to its earliest matching root, so SALARYCREDIT and SALARYBONUS both collapse to SAL for consistent reporting.
Understanding the Concepts
What is the Replace Words with Root problem?
Given a set of root words (a dictionary) and a sentence, replace every word in the sentence with the shortest root that is a prefix of it. If no root is a prefix of a word, leave it unchanged. For example, roots ["cat", "bat", "rat"] and sentence "the cattle was rattled by the battery" becomes "the cat was rat by the bat".
package com.bank.reporting;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ReplaceWordsWithRoot {
static class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isRoot = false;
}
private TrieNode root = new TrieNode();
public void insertRoot(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new TrieNode());
}
node.isRoot = true;
}
public String replaceWords(List<String> roots, String sentence) {
for (String r : roots) insertRoot(r);
StringBuilder result = new StringBuilder();
String[] words = sentence.split(" ");
for (int w = 0; w < words.length; w++) {
if (w > 0) result.append(" ");
result.append(findShortestRoot(words[w]));
}
return result.toString();
}
private String findShortestRoot(String word) {
TrieNode node = root;
StringBuilder prefix = new StringBuilder();
for (char c : word.toCharArray()) {
if (node.isRoot) return prefix.toString();
if (!node.children.containsKey(c)) return word;
node = node.children.get(c);
prefix.append(c);
}
return node.isRoot ? prefix.toString() : word;
}
}
Why does stopping at the first root node give the shortest match?
You walk the trie from the root, character by character. The trie structure preserves the order of characters. The first time you reach a node marked as a root, that root has the fewest characters among all matching roots. Any longer root that is also a prefix would be encountered later in the walk, but you have already stopped.
package com.bank.reporting;
public class ShortestMatchDemo {
public static void demonstrate() {
// Roots: ["sal", "salary", "sale"]
// Word: "salarycredit"
// Walk: s -> a -> l (marked as root!) → stop
// Result: "sal" (shortest match)
// "salary" is also a root and a prefix, but "sal" was found first
System.out.println("SALARYCREDIT → sal (stopped at first root node)");
}
}
How does the trie structure look?
Each node has a map of child characters and a boolean flag indicating whether it marks the end of a root word. The root of the trie represents the empty prefix.
package com.bank.reporting;
public class TrieStructureDemo {
public static void showStructure() {
// Roots: ["sal", "ren", "salary"]
//
// Trie:
// (root)
// ├── s
// │ └── a
// │ └── l [ROOT]
// │ └── a
// │ └── r
// │ └── y [ROOT]
// └── r
// └── e
// └── n [ROOT]
System.out.println("Trie built with 3 root words");
}
}
What happens when no root matches?
If at some character the trie has no matching child, no root is a prefix of the word, so you return the original word. Also, if you finish the word without hitting any root node, no root is a complete prefix, so you keep the original.
package com.bank.reporting;
public class NoMatchDemo {
public static void demonstrate() {
// Roots: ["sal", "ren"]
// Word: "payment"
// Walk: p → no child 'p' → return "payment" unchanged
// Word: "sa"
// Walk: s → a → end of word, but node not marked as root
// Return "sa" unchanged
}
}
What is the time and space complexity?
| Phase | Time | Space |
|---|---|---|
| Build trie | O(R) total root characters | O(R) trie nodes |
| Process sentence | O(S) total sentence characters | O(1) per word |
| Total | O(R + S) | O(R) |
How does this compare to brute-force prefix matching?
Without a trie, for each word you would check every root to see if it is a prefix, taking O(words * roots * avgLength). The trie reduces this to O(S) because each word is walked at most once through the trie, and the walk stops at the first root or at a missing child.
// Brute force: O(W * R * L) where W=words, R=roots, L=avg length
// Trie: O(S) where S=total sentence characters
// For 1000 words and 500 roots, trie is ~500x faster
What are edge cases?
Edge cases include an empty sentence (return empty), a word that is itself a root (return the word unchanged since it matches exactly), roots that are prefixes of other roots (the shortest one wins), and roots longer than any sentence word.
package com.bank.reporting;
import java.util.Arrays;
public class EdgeCases {
public static void test() {
ReplaceWordsWithRoot rw = new ReplaceWordsWithRoot();
// Word equals root: "sal" → "sal"
System.out.println(rw.replaceWords(Arrays.asList("sal"), "sal")); // "sal"
// Root longer than word: root "salary", word "sal" → "sal" (no match)
ReplaceWordsWithRoot rw2 = new ReplaceWordsWithRoot();
System.out.println(rw2.replaceWords(Arrays.asList("salary"), "sal")); // "sal"
}
}
sal
sal
What are common mistakes?
The most common mistake is not checking the root flag at the beginning of the loop iteration, which causes you to return one character too many. Another mistake is not handling the case where the word is shorter than any root.
package com.bank.reporting;
public class CommonMistakes {
// WRONG: check root flag after appending character
// This adds one extra character before detecting the root
// Fix: check node.isRoot BEFORE processing the next character
// WRONG: not handling short words
// Word "sa" with root "sal" → finish word before reaching root node
// Must return original word, not crash
}
How is this used in banking?
At the National Bank of India, the reporting team normalizes transaction descriptors down to their shortest registered root code. Descriptors like SALARYCREDIT, SALARYBONUS, and SALARYADVANCE all collapse to SAL, while RENTPAID and RENTALDEPOSIT collapse to REN. This gives consistent categorization for financial reports.
package com.bank.reporting;
import java.util.Arrays;
import java.util.List;
public class TransactionNormalizer {
public static void main(String[] args) {
ReplaceWordsWithRoot normalizer = new ReplaceWordsWithRoot();
List<String> roots = Arrays.asList("SAL", "REN", "PAY", "INT");
String descriptors = "SALARYCREDIT RENTPAID PAYMENTOUT INTERESTCREDIT MISCFEE";
String normalized = normalizer.replaceWords(roots, descriptors);
System.out.println("Normalized: " + normalized);
}
}
Normalized: SAL REN PAY INT MISCFEE
Visual Overview
Trie Structure
===============
Roots: ["sal", "ren", "salary"]
(root)
├── s
│ └── a
│ └── l [ROOT] ← stop here for "salarycredit"
│ └── a
│ └── r
│ └── y [ROOT]
└── r
└── e
└── n [ROOT] ← stop here for "rentpaid"
Prefix Walk for "SALARYCREDIT"
===============================
S → match child 's'
A → match child 'a'
L → match child 'l' → [ROOT] flag! STOP!
Return: "SAL" (3 chars consumed)
Remaining chars ARYCREDIT are never examined.
Prefix Walk for "MISCFEE"
==========================
M → no child 'm' in trie root → STOP!
Return: "MISCFEE" (original word, no match)
No-Match Cases
===============
┌────────────────────────────────────────┐
│ 1. No matching child → return word │
│ 2. Word ends before root → return word│
│ 3. Root found → return prefix │
└────────────────────────────────────────┘
Key Takeaway
Replace Words with Root is a prefix-matching application of the Trie data structure, and the elegant property is that stopping at the first root node along a word's path automatically gives the shortest matching root. You insert every root word into a trie and mark where each root ends, then for each word in the sentence you walk the trie from the root following the word's characters.
The moment you reach a node marked as a root, you stop and use the characters consumed so far as the replacement. If at some character the trie has no matching child, no root is a prefix of the word and you keep it unchanged. Each word costs time proportional to its own length (or the matching root length), so the whole sentence is linear in its total character count plus the size of the roots.
At the National Bank of India, the reporting team used this to normalize transaction descriptors down to their shortest registered root code. Descriptors like SALARYCREDIT and SALARYBONUS both collapsed to SAL, while RENTPAID and RENTALDEPOSIT collapsed to REN, giving consistent categorization for financial reports.
The key advantage over brute-force prefix matching is efficiency: checking every root against every word is O(words * roots * avgLength), while the trie reduces this to O(total characters) because each word is walked at most once through the trie.
Remember one sentence: walk each word through the trie and stop at the first node marked as a root, which is the shortest matching prefix.
---