# 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: “co*l”, “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);
}
}
}
```