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.

http://www.lintcode.com/en/problem/add-and-search-word/

Discussion

单词查找树（Trie），参考《算法第四版》5.2节。

Solution

// Time:  O(min(n, h)), per operation
// Space: O(min(n, h))
class WordDictionary {
public:
    struct TrieNode {
        bool is_word;
        unordered_map<char, TrieNode*> nodes;
    };
    WordDictionary() {
        _root = new TrieNode;
        _root-> is_word = true;
    }

    // Adds a word into the data structure.
    void addWord(string word) {
        TrieNode *cur = _root;
        for(int i=0; i<word.length(); i++) {
            if(cur->nodes.find(word[i]) == cur->nodes.end()) {
                cur->nodes[word[i]] = new TrieNode;
            }
            cur = cur->nodes[word[i]];
        }
        cur->is_word = true;
    }

    // Returns if the word is in the data structure. A word could
    // contain the dot character '.' to represent any one letter.
    bool search(string word) {
        return searchHelper(word, 0, _root);
    }
private:
    TrieNode *_root;
    bool searchHelper(string word, int pos, TrieNode *cur_node) {
        if(pos == word.length()) {
            return cur_node->is_word;
        }
        int i = pos;
        //就是从pos开始找，不是跟求subset一样有个循环在这里，写习惯了。。。
        if(cur_node->nodes.find(word[i]) != cur_node->nodes.end()) {
            return searchHelper(word, i+1, cur_node->nodes[word[i]]);
        } else if(word[i] == '.') {//dfs each element in cur_node->nodes
            for(auto const & v : cur_node->nodes) {
                if( searchHelper(word, i+1, v.second) ) {
                    return true;
                }
            }
        }
        return false;
    }
};

// Your WordDictionary object will be instantiated and called as such:
// WordDictionary wordDictionary;
// wordDictionary.addWord("word");
// wordDictionary.search("pattern");