[LintCode] Add and Search Word

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);
    }
};