Leetcode: Add and Search Word - Data structure design

方法1：brute force: search function compares each word with the pattern, time complexity: O(nk), n is number of words in dictionary, k is averge length

方法2: trie, search use recursion, time complexity: O(nk)? space O(nk)?

This is related to previous problem: Implement Trie

Only because in this problem, "." is introduced, which will cause us to backtrack to check each son. Using iteration is not that convient, we use recursion here.

One thing to be cautious is that when inserting words to a trie, the last node should have node.isEnd set to be true. Always forget this

Follow Up: any other solution?

1. Preprocess the dictionary, store map<key, set<words>>, key is the pattern, like ".a.e.c", time complexity O(1), space complexity O(2^k), k is average word length

2. still use trie, but for each trieNode, introduce a child '.', in the meanwhile maintain a set of words matched by current prefix, time complexity O(k), space: each level's space will be twice the orignal trie's space of this level.

Follow Up: 如果现在word里面包含的不再是'.', 而是‘*’, 能match 0个到多个字符，问该怎么处理？

 完整代码在这里：

The current adopted way of implement Trie: without val and num field