目录

0211:添加与搜索单词 - 数据结构设计(★)

力扣第 211 题

题目

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

实现词典类 WordDictionary

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

示例:

输入:
["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 由 '.' 或小写英文字母组成
  • 最多调用 104addWordsearch

相似问题:

分析

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