211. Add and Search Word – Data structure design 211. Add and Search Word – Data structure design

Design a data structure that supports the following two operations:

void addWord(word)
bool 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") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Note:
You may assume that all words are consist of lowercase letters a-z. 211. Add and Search Word – Data structure design

---

实现一个字典，要求可以插入单词和搜索单词，并且支持一种正则表达式，即点号’.’表示任意一个字符。 本题明显是用Trie树来做，插入和搜索普通字符串的方法和Trie树是一模一样的。 唯一需要注意的是搜索带点号的字符串，此时用递归来做，递归的出口是，当遍历到字符串的最后一个字符时，根据是否为点号进行判断。递归向下的过程也是分是否为点号的，如果是点号，则需要尝试26种递归路径。想清楚这个逻辑之后，代码就很好写了。 完整代码如下：

const int N = 26;
class WordDictionary {
private:
    struct Node {
        bool isWord;
        vector<Node*> children;
        Node(bool i)
            : isWord(i)
        {
            for (int i = 0; i < N; ++i)
                children.push_back(NULL);
        };
    };
    Node* root;
    bool search(const string& word, int i, Node* root)
    {
        if (root == NULL)
            return false;
        int idx = word[i] – ‘a’;
        if (i == word.size() – 1) {
            if (word[i] != ‘.’)
                return root->children[idx] != NULL && root->children[idx]->isWord;
            else {
                for (int j = 0; j < N; ++j) {
                    if (root->children[j] != NULL && root->children[j]->isWord)
                        return true;
                }
                return false;
            }
        }
        if (word[i] != ‘.’)
            return search(word, i + 1, root->children[idx]);
        else {
            for (int j = 0; j < N; ++j) {
                if (search(word, i + 1, root->children[j]))
                    return true;
            }
            return false;
        }
    }
public: /** Initialize your data structure here. */
    WordDictionary() { root = new Node(false); } /** Adds a word into the data structure. */
    void addWord(string word)
    {
        Node* cur = root;
        for (const auto& c : word) {
            int idx = c – ‘a’;
            if (cur->children[idx] == NULL)
                cur->children[idx] = new Node(false);
            cur = cur->children[idx];
        }
        cur->isWord = 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)
    {
        Node* cur = root;
        return search(word, 0, cur);
    }
};

本代码提交AC，用时105MS。