LeetCode - 解题笔记 - 211 - Design Add and Search Words Data Structure

Solution 1

根据数据结构的功能，可以基本判定其内部实现是一个前缀树，可以使用 0208. Implement Trie (Prefix Tree) 作为基础。

但是本题额外引入了一个通配符，一个通配符对应一个字符位，因此我们需要通过DFS枚举搜索。

本题在实现中遇到了一个奇怪的剪枝优化：如果当前搜索位不是通配符，仍然需要对枚举结果进行判定。否则会出现TLE的问题（实测是OJ的耗时玄学……）

• 时间复杂度：$O(R^N)$，其中$N$为查询字符的长度，$R$为基数。最坏情况下所有的搜索位都是通配符，全展开搜索。本题条件将通配符数量限制到3，因此实际为$O(N)$
• 空间复杂度：$O(MN)$，其中$N$为查询字符的长度，$M$为输入的字符串个数。DFS的搜索占用仅需要一个$O(N)$

class Trie {
   
private:
    vector<Trie*> next;
    const int R = 26;
    bool isEnd;
    
public:
    Trie() {
   
        next = vector<Trie*>(this->R);
        isEnd = false;
    }
    
    void insert(string word) {
   
        auto node = this;
        for (char c: word) {
   
            if (node->next[c - 'a'] == nullptr) {
   
                // 不存在，直接插入
                node->next[c - 'a'] = new Trie();
            }
            node 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24