题目描述

请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配。

实现词典类 WordDictionary：

• WordDictionary() 初始化词典对象。
• void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配。
• bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true；否则，返回 false。word 中可能包含一些 '.'，每个 .. 都可以表示任何一个字母。

样例

输入：
["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
输出：
[null,null,null,null,false,true,true,true]

解释：
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // 返回 False
wordDictionary.search("bad"); // 返回 True
wordDictionary.search(".ad"); // 返回 True
wordDictionary.search("b.."); // 返回 True

限制

• 1 <= word.length <= 25
• addWord 中的 word 由小写英文字母组成。
• search 中的 word 由 '.' 或小写英文字母组成。
• 最多调用 10^4 次 addWord 和 search。

算法

(字典树 + 深度优先搜索) 插入 $O(L)$；查询 $O(S)$

1. 对每个新加入的字符串插入到字典树中。
2. 查询时在字典树上进行深度优先搜索，搜索的状态记录当前结点以及对应字符串中哪个字符。对于通配符，则递归遍历当前结点的所有子结点。

时间复杂度

• 插入的时间复杂度长度 $L$ 有关，故插入的时间复杂度为 $O(L)$。
• 查询时，由于存在通配符，最坏情况下会遍历整棵字典树，故查询的时间复杂度为 $O(S)$，其中 $S$ 为字典树中字符的数量，不超过 $nL$。

空间复杂度

• 需要额外的空间存放字典树和队列。
• 故空间复杂度为 $O(S)$，其中 $S$ 为字典树中字符的数量，不超过 $nL$。

C++ 代码

const int N = 10010;

struct Node {
    int ch[26];
    bool end;

    Node() {
        memset(ch, 0, sizeof(ch));
        end = false;
    }
};

class WordDictionary {
public:
    Node node[N * 25];
    int root, cnt;

    WordDictionary() {
        root = 1;
        cnt = 2;
    }

    void addWord(string word) {
        int p = root;
        for (char c: word) {
            if (!node[p].ch[c - 'a'])
                node[p].ch[c - 'a'] = cnt++;

            p = node[p].ch[c - 'a'];
        }

        node[p].end = true;
    }

    bool dfs(int i, int p, const string &word) {
        if (i == word.size())
            return node[p].end;

        if (word[i] != '.') {
            if (!node[p].ch[word[i] - 'a'])
                return false;

            return dfs(i + 1, node[p].ch[word[i] - 'a'], word);
        }

        for (int c = 0; c < 26; c++)
            if (node[p].ch[c] && dfs(i + 1, node[p].ch[c], word))
                return true;

        return false;
    }

    bool search(string word) {
        return dfs(0, root, word);
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */