LC 211. 添加与搜索单词 - 数据结构设计

题目描述

这是 LeetCode 上的 211. 添加与搜索单词 - 数据结构设计 ，难度为 中等。

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

实现词典类 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
16
输入：
["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 <= word.length <= 500$
  • addWord 中的 word 由小写英文字母组成
  • search 中的 word 由 '.' 或小写英文字母组成
  • 最多调用 $50000$ 次 addWord 和 search

基本分析

一道 $Trie$ 的轻度变形模板题，还不熟悉 $Trie$ 的同学可以看 这里，里面详细介绍了实现 $Trie$ 的两种方式、注意事项以及 $Trie$ 应用面等等，是解决本题的前置芝士 🧀。

简单回顾一下：

$Trie$ 树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。

其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后续字符串的字符是什么」。

IMG_1659.PNG

回到本题，首先 addWord 操作不会带 . 符号，因此我们采用原有的 $Trie$ 插入方式即可；而在 search 操作中会有 . 符号，我们需要枚举某个 . 所代指的字母是什么，这需要结合 DFS 来做。

二维数组

使用数组实现，需要预先估算数组大小。

通常估算值会很大，直接使用估算值会 MLE。利用 $Trie$ 会有很多位置被共用，以及合格的测试用例，应该至少做到「查询」调用次数和「插入」调用次数相当，我们可以使用比估算值小的数（往下调整一个数量级），更详细的估算逻辑在 前置芝士 讲过，不再赘述。

使用数组实现，还有一个可优化的地方是使用 static 修饰所有用到的数组，然后在初始化 Solution 的时候做清理工作，这样可以有效避免跑每个样例都创建大数组。

实际测试使用 static 与否执行时间会相差超过一半。

代码（$P1$ 带 static 优化）:

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
class WordDictionary {
    static int N = 250000;
    static int[][] tr = new int[N][26];
    static boolean[] isWord = new boolean[N];
    static int idx;
    public WordDictionary() {
        for (int i = 0; i < idx; i++) {
            Arrays.fill(tr[i], 0);
        }
        Arrays.fill(isWord, false);
        idx = 0;
    }
    public void addWord(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        isWord[p] = true;
    }
    public boolean search(String s) {
        return dfs(s, 0, 0);
    }
    boolean dfs(String s, int trIdx, int sIdx) {
        int n = s.length();
        if (n == sIdx) return isWord[trIdx];
        char c = s.charAt(sIdx);
        if (c == '.') {
            for (int j = 0; j < 26; j++) {
                if (tr[trIdx][j] != 0 && dfs(s, tr[trIdx][j], sIdx + 1)) return true;
            }
            return false;
        } else {
            int u = c - 'a';
            if (tr[trIdx][u] == 0) return false;
            return dfs(s, tr[trIdx][u], sIdx + 1);
        }
    }
}

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
class WordDictionary {
    int N = 250000;
    int[][] tr = new int[N][26];
    boolean[] isWord = new boolean[N];
    int idx;
    public void addWord(String s) {
        int p = 0;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        isWord[p] = true;
    }
    public boolean search(String s) {
        return dfs(s, 0, 0);
    }
    boolean dfs(String s, int trIdx, int sIdx) {
        int n = s.length();
        if (sIdx == n) return isWord[trIdx];
        char c = s.charAt(sIdx);
        if (c == '.') {
            for (int j = 0; j < 26; j++) {
                if (tr[trIdx][j] != 0 && dfs(s, tr[trIdx][j], sIdx + 1)) return true;
            }
            return false;
        } else {
            int u = c - 'a';
            if (tr[trIdx][u] == 0) return false;
            return dfs(s, tr[trIdx][u], sIdx + 1);
        }
    }
}
  • 时间复杂度：$L$ 为字符串的最大长度，addWord 操作的复杂度为 $O(L)$；search 操作的复杂度为 $O(C * L)$，其中 $C$ 为字符集大小，固定为 $26$
  • 空间复杂度：静态数组大小固定，复杂度为 $O(1e7)$

TrieNode

同理，我们也能够使用 $TrieNode$ 的方式实现。

好处是不需要进行数组大小估算，但是不可避免需要在一个样例中执行多次 $new$ 动作。

代码：

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
class WordDictionary {
    class Node {
        Node[] tns = new Node[26];
        boolean isWord;
    }
    Node root = new Node();
    public void addWord(String s) {
        Node p = root;
        for (int i = 0; i < s.length(); i++) {
            int u = s.charAt(i) - 'a';
            if (p.tns[u] == null) p.tns[u] = new Node();
            p = p.tns[u];
        }
        p.isWord = true;
    }
    public boolean search(String s) {
        return dfs(s, root, 0);
    }
    boolean dfs(String s, Node p, int sIdx) {
        int n = s.length();
        if (n == sIdx) return p.isWord;
        char c = s.charAt(sIdx);
        if (c == '.') {
            for (int j = 0; j < 26; j++) {
                if (p.tns[j] != null && dfs(s, p.tns[j], sIdx + 1)) return true;
            }
            return false;
        } else {
            int u = c - 'a';
            if (p.tns[u] == null) return false;
            return dfs(s, p.tns[u], sIdx + 1);
        }
    }
}

  • 时间复杂度：addWord 操作的复杂度为 $O(L)$；search 操作的复杂度为 $O(C * L)$，其中 $C$ 为字符集大小，固定为 $26$
  • 空间复杂度：令 n 为插入字符串数量，$L$ 为字符串的最大长度，复杂度为 $O(n * L)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.211 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。