Question
Given a trie data struture, implement add() and search() method, which support wildcard matching.
eg. If trie contains [“cool”, “kid”, “kindle”, “kind”]
These would match: “col”, “kind”, “**”
These won’t: “*”, “kid”, “coo”
Solution
First, know how to build a trie, then know how to search in Trie. This could be tricky. Do Read On!
- Trie (root) start with an empty node.
- When do searching, ALWAYS assumes that current TrieNode is matched. I.e. do not check value of current TrieNode. Instead, check current TrieNode’s children, and find a match.
- The only case you return true, is when matching reaches current TrieNode, and current TrieNode is an terminating node for a word.
- Be careful and do not confuse yourself for which node you gonna match, and when you return true.
Read the code below. If you still have a hard time, read #2 and #3 above, again.
Code
public boolean solve(TrieRoot trie, String word) {
if (word == null || word.length() == 0) {
return false;
}
return matchFromChildren(trie.getRoot(), word, 0);
}
private boolean matchFromChildren(TrieNode node, String word, int index) {
// [important note]
// regardless of the value of node.letter, match word[index...] from node.children
if (index > word.length()) {
// impossible to reach here
return false;
} else if (index == word.length()) {
// word is now fully matched, check if isTerminalNode(node)
return node.isEndOfWord();
}
char curLetter = word.charAt(index);
if (curLetter == '*') {
for (TrieNode child: node.getAllChildren()) {
if (matchFromChildren(child, word, index + 1)) {
return true;
}
}
return false;
} else {
TrieNode nextNode = node.getChild(curLetter);
if (nextNode == null) {
return false;
} else {
return matchFromChildren(nextNode, word, index + 1);
}
}
}
