题目描述

题目链接

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

实现词典类 WordDictionary ：

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

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
输入：
["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"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

算法1

(结构体构造Trie树 + 暴力搜索dfs) $O(n)$

常规解法与 Tire 树类似，仅需要完全遍历所有的单词，因此时间复杂度是 $O(n)$ 级别，但是由于题目中加入了正则表达式匹配规则，那么在遇到 ‘.’ 时需要对其后的所有单词进行遍历搜索， 仍然是 $O(n)$ 时间复杂度

分类讨论：

  • 当前的字符不是 ‘.’ 时，按照正常的 Trie 树来遍历
  • 当前字符是 ‘.’ 时，需要进行深度优先搜索，枚举这个点所有可能的方案( a - z) ，如果其中有一条结果成功匹配，那么返回 true，若所有结果都失败，返回 false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class WordDictionary {
public:
    struct Node {
        bool is_end;
        Node* son[26];
        Node () {
            is_end = false;
            for(int i = 0; i < 26; i ++)
                son[i] = NULL;
        }
    } *root;

    WordDictionary() {
        root = new Node();
    }
    
    void addWord(string word) {
        auto p = root;
        for(auto c : word)
        {
            int u = c - 'a';
            if( !p->son[u]) p->son[u] = new Node();
            p = p->son[u];
        }
        p->is_end = true;
    }
    
    bool search(string word) {
        return dfs(root, word, 0);
    }

    bool dfs(Node* p, string& word, int i)
    {
        if( i == word.size()) return p->is_end;
        if( word[i] != '.')
        {
            int u = word[i] - 'a';
            if( !p->son[u]) return false;
            return dfs(p->son[u], word, i + 1);
        }
        else
            for(int j = 0; j < 26; j ++)
            {
                if(p->son[j] && dfs(p->son[j], word, i + 1))
                    return true;
            }
        return false;
    }
};

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