Design Add and Search Words Data Structure

211. 添加与搜索单词

分析

构建 Trie 树
- Node 节点中包含：
  - 一个 son[26] 数组，用于存储 26 个字母子节点指针
  - 一个 ended 布尔变量，标记当前节点是否为某单词的结尾
- addWord() 操作：
  - 从根节点出发，逐字符插入 Trie 中，不存在的节点创建新的子节点
  - 插入完成后将末尾节点标记为单词结束
实现查找逻辑
- search() 方法调用 dfs() 深搜判断是否能匹配给定单词
DFS 搜索策略
- 遇到普通字符：检查对应子节点是否存在，递归查找下一字符
- 遇到 .：遍历所有子节点，若任一分支匹配成功即可返回 true
- 若遍历结束时抵达有效单词结尾，则返回 true

时间复杂度

addWord(word)：O(L)，其中 L 是单词长度
search(word)：
- 普通查找：O(L)
- 含 . 的查找：最坏情况 O(26^L)

空间复杂度

O(N \times L)，N 为单词数量，L 为单词平均长度

C++代码

 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


class WordDictionary
{
public:
    struct Node {
        Node() {
            ended = false;
            for (int i = 0; i < 26; ++i)
                son[i] = nullptr;
        }
        Node* son[26];  // 子节点数组
        bool ended;     // 标记单词结束
    };

    Node* root;

    WordDictionary() {
        root = new Node();
    }

    // 插入单词
    void addWord(string word) {
        Node* p = root;
        for (char c : word) {
            int u = c - 'a';
            if (!p->son[u])
                p->son[u] = new Node();
            p = p->son[u];
        }
        p->ended = true;
    }

    // 查找单词
    bool search(string word) {
        return dfs(root, word, 0);
    }

    // 深度优先搜索实现查找逻辑
    bool dfs(Node* p, std::string word, int i) {
        if (i == word.size())
            return p->ended;  // 抵达单词末尾，判断是否有效
        if (word[i] != '.') {
            int u = word[i] - 'a';
            if (p->son[u])
                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;
    }
};