Definition
- Trie (prefix tree) – a tree where each node holds child links for characters and an end-of-word flag; inserting a word walks or creates nodes character by character.
- Wildcard dot – the character
.matches any single letter, so during search it branches into all children of the current node. - DFS search – a recursive traversal that follows one child for a normal character and fans out to all children for a dot, returning true if any branch reaches an end-of-word at the pattern's end.
- End-of-word check – the base case when the pattern index reaches the end; the search succeeds only if the current node is marked as a word ending, not merely a prefix.
- Branching cost – with no dots, search is O(L) where L is the word length; each dot multiplies branching by the number of children at that level.
At the National Bank of India, support agents look up stored transaction references when a customer recites one imperfectly, typing a dot wherever they cannot recall a character. A known character takes one exact drawer in the reference directory, while a dot means try every drawer at that level. If one of the branching paths spells a complete stored reference, the lookup succeeds.
Understanding the Concepts
What is a Trie and how does it support this problem?
A Trie, also called a prefix tree, is a tree data structure where each node represents a character in a string and holds child links for the next characters. Inserting a word walks from the root, creating child nodes as needed, and marks the final node as an end-of-word. This structure allows prefix-based lookups in time proportional to the word length.
For the National Bank of India, Rajesh builds a Trie of transaction reference codes so support agents can search for references that match a partial pattern.
package com.bank.service;
import java.util.HashMap;
import java.util.Map;
public class WordDictionary {
private static class TrieNode {
Map<Character, TrieNode> children = new HashMap<>();
boolean isEndOfWord = false;
}
private final TrieNode root = new TrieNode();
public void addWord(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new TrieNode());
}
node.isEndOfWord = true;
}
}
How does the wildcard search work?
Search is a recursive depth-first traversal parameterised by the current index in the pattern and the current Trie node. When the pattern character is a normal letter, the search follows exactly one child link matching that letter. When the character is a dot, the search fans out to every child of the current node and succeeds if any branch succeeds. The base case is when the index reaches the end of the pattern, at which point the search returns whether the current node is marked as an end-of-word.
public boolean search(String word) {
return dfs(word, 0, root);
}
private boolean dfs(String word, int index, TrieNode node) {
if (index == word.length()) {
return node.isEndOfWord; // must be a complete word, not just a prefix
}
char c = word.charAt(index);
if (c == '.') {
// Dot: try every child
for (TrieNode child : node.children.values()) {
if (dfs(word, index + 1, child)) return true;
}
return false;
} else {
// Normal character: follow one exact child
TrieNode child = node.children.get(c);
return child != null && dfs(word, index + 1, child);
}
}
Why does the dot fan out to all children instead of iterating characters?
The dot must try every possible character at that position, but we do not know which characters exist. Instead of iterating over all 26 lowercase letters and checking each one, we iterate over the children map, which contains only the characters that actually have entries. This is more efficient because a node typically has far fewer than 26 children.
This matters in the banking domain because the reference code alphabet might include digits and letters, making a fixed iteration over all characters wasteful.
package com.bank.service;
public class DotFanOutDemo {
// Iterating node.children.values() is better than:
// for (char ch = 'a'; ch <= 'z'; ch++) {
// TrieNode child = node.children.get(ch);
// if (child != null && dfs(...)) return true;
// }
// Because children.values() only visits existing children.
public static void main(String[] args) {
WordDictionary dict = new WordDictionary();
dict.addWord("TXN001");
dict.addWord("TXN002");
dict.addWord("REF001");
System.out.println(dict.search("TXN001")); // true: exact match
System.out.println(dict.search("TXN.01")); // true: dot matches 0
System.out.println(dict.search("...001")); // true: dots match T, X, N
System.out.println(dict.search("ABC001")); // false: no such prefix
}
}
true
true
true
false
How is this different from a regular Trie search?
| Feature | Regular Trie search | Wildcard Trie search |
|---|---|---|
| Character handling | follow one exact child | follow one child for letter, all children for dot |
| Time for length L | O(L) | O(L) best case, O(N * L) worst case with all dots |
| Recursion | iterative or recursive | must be recursive (DFS for branching) |
| Use case | autocomplete, prefix check | pattern matching with unknown characters |
package com.bank.service;
public class TrieComparisonDemo {
public static void main(String[] args) {
WordDictionary dict = new WordDictionary();
dict.addWord("loan");
dict.addWord("lore");
dict.addWord("loft");
// Regular search: follows one path, O(L)
System.out.println(dict.search("loan")); // true
// Wildcard search: dot at index 2 fans out to a, r, f
System.out.println(dict.search("lo.n")); // true (matches loan)
System.out.println(dict.search("lo.e")); // true (matches lore)
System.out.println(dict.search("lo.x")); // false (no match)
}
}
true
true
true
false
What are the rules and constraints?
The addWord method receives only lowercase English letters. The search method receives lowercase English letters and the dot character. Both words and patterns have length between 1 and 25. The data structure can hold up to 10,000 words. The end-of-word check at the base case is critical: without it, a prefix that is not a complete word would falsely match.
package com.bank.service;
public class EndOfWordImportance {
public static void main(String[] args) {
WordDictionary dict = new WordDictionary();
dict.addWord("payment");
// "pay" is a prefix of "payment" but not a stored word
System.out.println(dict.search("pay")); // false: not end-of-word
System.out.println(dict.search("payment")); // true: end-of-word
System.out.println(dict.search("pa.ment")); // true: dot matches y
}
}
false
true
true
What are the edge cases?
Edge cases include a search pattern that is entirely dots, which must fan out at every level and could explore a large part of the Trie. Another edge case is searching for a word that was never added, where the search should fail gracefully at the first missing child link. A third edge case is adding the same word twice, which should not change behaviour because the end-of-word flag is already set.
package com.bank.service;
public class TrieEdgeCases {
public static void main(String[] args) {
WordDictionary dict = new WordDictionary();
dict.addWord("emi");
dict.addWord("emi"); // duplicate add: no change
System.out.println(dict.search("...")); // true: all dots match e, m, i
System.out.println(dict.search("....")); // false: pattern too long
System.out.println(dict.search("xyz")); // false: no such word
System.out.println(dict.search(".m.")); // true: matches emi
}
}
true
false
false
true
What are common mistakes?
The most common mistake is forgetting the end-of-word check at the base case, which causes the search to match prefixes that are not complete words. Another mistake is not handling the dot case by iterating the children map and instead trying to iterate all 26 letters, which is wasteful. A third mistake is returning false too early in the dot case without trying all children.
Wrong code that skips end-of-word check:
// WRONG: returns true even for prefixes
private boolean dfsBad(String word, int index, TrieNode node) {
if (index == word.length()) {
return true; // BUG: should check node.isEndOfWord
}
// ... rest of search
}
Correct code:
// CORRECT: only matches complete words
private boolean dfsGood(String word, int index, TrieNode node) {
if (index == word.length()) {
return node.isEndOfWord; // must be a word ending
}
// ... rest of search
}
What should a senior engineer know?
A senior engineer knows that the worst-case search time with all dots is O(N * L) where N is the total number of nodes and L is the pattern length, because every dot branches into all children. In production, they would limit the number of dots allowed or add a timeout. They also know that using a char[26] array instead of a HashMap for children trades memory for faster lookups, and that this data structure is the foundation of regex engines, spell checkers, and autocomplete systems.
package com.bank.service;
public class TrieArrayOptimisation {
// Array-based TrieNode: faster lookups, fixed 26-char alphabet
static class FastTrieNode {
FastTrieNode[] children = new FastTrieNode[26];
boolean isEndOfWord = false;
}
static FastTrieNode root = new FastTrieNode();
static void addWord(String word) {
FastTrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new FastTrieNode();
}
node = node.children[idx];
}
node.isEndOfWord = true;
}
public static void main(String[] args) {
addWord("transfer");
addWord("transaction");
System.out.println("Added words to array-based Trie");
}
}
Added words to array-based Trie
Visual Overview
Trie Structure After Adding: loan, lore, loft
root
│
┌─▼─┐
│ l │
└─┬─┘
│
┌─▼─┐
│ o │
└─┬─┘
┌────┼────┐
┌─▼─┐┌─▼─┐┌─▼─┐
│ a ││ r ││ f │
└─┬─┘└─┬─┘└─┬─┘
┌─▼─┐┌─▼─┐┌─▼─┐
│ n*││ e*││ t*│ * = end-of-word
└───┘└───┘└───┘
Search: lo.n
Step 1: l -> follow exact child 'l'
Step 2: o -> follow exact child 'o'
Step 3: . -> fan out to ALL children: a, r, f
Branch a: check 'n' in children of 'a' -> found, isEndOfWord=true => MATCH
Branch r: check 'n' in children of 'r' -> not found => fail
Branch f: check 'n' in children of 'f' -> not found => fail
Result: true (one branch succeeded)
Key Takeaway
This problem extends a plain Trie with a search that understands the dot wildcard, which matches any single character. Adding a word is ordinary Trie insertion: walk the word from the root, create missing child nodes, and mark the final node as an end-of-word. The interesting part is the search.
Search is a recursive depth-first traversal parameterised by the current pattern index and the current node. When the pattern character is a normal letter, follow exactly one child link, failing if it does not exist. When the character is a dot, try every child of the current node and succeed if any recursive call succeeds, which is the fan-out that makes wildcards work. The base case is when the index reaches the end of the pattern, where the search returns whether the current node is marked as an end-of-word, not merely a prefix.
The cost with no dots is O(L) for a pattern of length L. Each dot multiplies branching by the number of children at that level, so a pattern of all dots could explore a large part of the Trie. In production, Rajesh limits the number of dots allowed or adds a timeout to protect the service.
At the National Bank of India, support agents used this to look up stored transaction references when a customer recited one imperfectly. The known characters pruned the search down one exact path, and only the unknown positions fanned out, so the lookup stayed focused on plausible references. The end-of-word check ensured that partial matches to longer references did not produce false positives.
Remember one sentence: insert words into a Trie normally, and search with DFS where a dot fans out to all children while a real character follows one, succeeding only when a branch reaches an end-of-word marker.
---