0211：添加与搜索单词 - 数据结构设计（★）

力扣第 211 题

题目

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

实现词典类 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 由 '.' 或小写英文字母组成
• 最多调用 104 次 addWord 和 search

相似问题：

• 0208：实现 Trie (前缀树)
• 0745：前缀和后缀搜索
• 2301：替换字符后匹配（1860 分）
• 2416：字符串的前缀分数和（1725 分）
• 3045：统计前后缀下标对 II（2327 分）
• 3042：统计前后缀下标对 I（1214 分）

分析

0208 升级版，search 里可能含有 ‘.’，分别递归即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class WordDictionary:

    def __init__(self):
        T = lambda:defaultdict(T)
        self.trie = T()

    def addWord(self, word: str) -> None:
        p = self.trie
        for c in word:
            p = p[c]
        p['#'] = {}

    def search(self, word: str) -> bool:
        def dfs(p,i):
            if i==len(word):
                return True
            if word[i]=='.':
                return any(dfs(q,i+1) for q in p.values())
            return word[i] in p and dfs(p[word[i]],i+1)

        word += '#'
        return dfs(self.trie,0)

1207 ms