You are building the word list for a crossword helper. It can save words. Later it can answer a pattern search. In a pattern, a dot . stands for any one letter.
A saved word matches a pattern only when both have the same length. Each letter must be equal, unless the pattern has a dot at that place.
Write a class WordDictionary with these methods:
WordDictionary(): make an empty dictionary.addWord(word): save word for later searches.search(word): return true if at least one saved word matches the pattern word. Otherwise, return false. The pattern may have dots.
Examples
Example 1:
Input
["WordDictionary", "addWord", "addWord", "addWord", "search", "search", "search", "search", "search"]
[[], ["tea"], ["ten"], ["tent"], ["te"], ["te."], ["t.n"], ["..nt"], ["..."]]
Output
[null, null, null, null, false, true, true, true, true]
Explanation
The saved words are tea, ten and tent.
search("te") is false, because no saved word has 2 letters.
search("te.") is true, it matches tea and ten.
search("t.n") is true, it matches ten.
search("..nt") is true, it matches tent.
search("...") is true, it matches tea and ten.
Example 2:
Input
["WordDictionary", "search", "addWord", "search", "search", "addWord", "search"]
[[], ["a"], ["a"], ["a"], ["."], ["bat"], [".a."]]
Output
[null, false, null, true, true, null, true]
Explanation
The dictionary is empty at first, so search("a") is false.
After addWord("a"), both search("a") and search(".") are true.
After addWord("bat"), search(".a.") is true, because it matches bat.