Design a data structure that supports adding words and searching words with '.' wildcard characters. Pattern focus: Wildcard Search with Trie (Add and Search Words). The wildcard branch must explore all possible matching children only when necessary.
operations = add/search commands, values = words or patterns
boolean results for each search command in order
Example 1:
Input:
operations = ["add","add","search","search","search","search"] values = ["bad","dad","pad","bad",".ad","b.."]
Output:
[false,true,true,true]
Explanation:
The wildcard search should match any single character in place of '.'.
Example 2:
Input:
operations = ["search"] values = ["."]
Output:
[false]
Explanation:
Searching before any insert should fail.
Example 3:
Input:
operations = ["add","add","search","search","search","search"] values = ["at","and","a","a.",".n","b."]
Output:
[false,true,false,false]
Explanation:
Exact matches, wildcard matches, and failing patterns can coexist in the same query list.