Design a data structure that supports the following two operations:
addWord(word)
and search(word)
search(word)
can search a literal word or a regular expression string containing only letters a-z
or .
.
A
.
means it can represent any one letter.
Example
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") // return false
search("bad") // return true
search(".ad") // return true
search("b..") // return true
Note
You may assume that all words are consist of lowercase letters a-z.
class Trie { unordered_map<char,Trie*> _map; bool _end; public: Trie() { _end = false; } void add(string &s,int n) { if(!_map.count(s[n])) { _map[s[n]] = new Trie(); } if(n == s.length() - 1) { _map[s[n]]->_end = true; } else { _map[s[n]]->add(s, n+1); } } bool search(string &s, int n){ if(s.length() -1 == n) { if(s[n] == '.') { for(auto e : _map) { if(e.second->_end) return true; } return false; } return _map.count(s[n]) ? _map[s[n]]->_end : false; } if(s[n] == '.') { for(auto e : _map) { if(e.second->search(s, n+1)) { return true; } } } else { if(!_map.count(s[n])) return false; return _map[s[n]]->search(s, n+1); } return false; } }; class WordDictionary { Trie _trie; public: void addWord(string word) { _trie.add(word, 0); } bool search(string word) { return _trie.search(word, 0); } };