原题

LintCode 473. Add and Search Word

Description

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.

Notice

You may assume that all words are consist of lowercase letters a-z.

Example

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") // return false
search("bad") // return true
search(".ad") // return true
search("b..") // return true

解题

利用Trie，即字典树解决。字典树中的每个节点有26个子节点，代表接下来的26个字母所在的节点，另外每个节点还有一个变量isWord来表示该节点是不是一个单词的结尾。

插入过程：对于单词中的每个字母，从根节点出发，如果这个字母所对应的子节点不存在，则生成它。然后在该子节点上对下一个字母继续上述过程。直到所有的字母都被处理，此时在最后一个字母所对应的节点上，设置isWord为true

搜索过程：不考虑通配符的情况下，只需要从根节点开始遍历字母所在的子节点：

• 如果某个字母对应的节点不存在，说明这个这个单词在树中不存在，返回false
• 如果所有字母的节点都存在，但是最后一个字母的节点isWord不为true，说明以当前单词为前缀的单词存在，但是并不是这个单词本身，返回false
• 如果租后一个字母的节点isWord为true，则返回true

考虑通配符的情况，需要对上述过程进行简单修改。如果找到某个字母是通配符.，那么遍历当前所在节点的所有存在的子节点。

代码

struct TrieNode {
    bool isKey = false;
    TrieNode* child[26];
};

class WordDictionary {
public:
    /*
    * @param word: Adds a word into the data structure.
    * @return: nothing
    */
    void addWord(string &word) {
        // write your code here
        TrieNode *current = root;
        for (auto c : word) {
            int index = c - 'a';
            if (current->child[index] == nullptr) {
                current->child[index] = new TrieNode();
            }
            current = current->child[index];
        }
        current->isKey = true;
    }

    /*
    * @param word: A word could contain the dot character '.' to represent any one letter.
    * @return: if the word is in the data structure.
    */
    bool search(string &word) {
        // write your code here
        return helper(word, root);
    }
private:
    TrieNode *root = new TrieNode();
    bool helper(string word, TrieNode *r) {
        if (word.size() == 0) return r->isKey;
        string sub = word.substr(1);
        if (word.front() == '.') {
            for (TrieNode* node : r->child) {
                if (node && helper(sub, node)) return true;
            }
            return false;
        } else {
            int index = word.front() - 'a';
            return r->child[index] && helper(sub, r->child[index]);
        }
    }
};

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