TrieDesignDFS
Build a dictionary with two operations: add w stores a word, and search p reports whether any stored word matches the pattern p. In a pattern the character . stands for any single letter. You are given a list of operations to run.
Input
Line 1: q, the number of operations. Next q lines: add w or search p (lowercase letters, and . in patterns).
Output
For every search print true or false, one per line.
Constraints
1 <= q <= 10^4 1 <= length of each word or pattern <= 20
Example 1
Input
6 add bad add dad add mad search pad search bad search .ad
Output
false true true
pad is not stored, bad is, and .ad matches bad, dad and mad.