211.添加与搜索单词.md

211.添加与搜索单词

https://leetcode-cn.com/problems/design-add-and-search-words-data-structure/solution/211tian-jia-yu-sou-suo-dan-ci-zi-dian-sh-u9lb/

难度：中等

题目：

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

实现词典类 WordDictionary ：

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

提示：

• 1 <= word.length <= 500
• addWord 中的 word 由小写英文字母组成
• search 中的 word 由 '.' 或小写英文字母组成
• 最多调用 50000 次 addWord 和 search

示例：

输入：
["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

分析

这道题本该是考察前缀树的题目，但由于存在.的模糊匹配，导致了前缀树的效率并不怎么高。 当存在多个.时，前缀树就比较鸡肋了，反而通过字符串长度来保存模板字符串，效率更高些。

前缀树解题：

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.tree = {}

    def addWord(self, word: str) -> None:
        tmp = self.tree
        for w in word:
            if w not in tmp:
                tmp[w] = {}
            tmp = tmp[w]
        tmp['_end'] = True

    def search(self, word: str) -> bool:
        tmp = self.tree
        for i in range(len(word)):
            if word[i] == '.':
                for k in tmp.keys():
                    if self.search(word[:i] + k + word[i+1:]):
                        return True
                return False
            elif word[i] in tmp:
                tmp = tmp[word[i]]
            else:
                return False
        return tmp.get('_end', False)

根据长度定义字典

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.tree = {}

    def addWord(self, word: str) -> None:
        ln = len(word)
        if ln not in self.tree:
            self.tree[ln] = [word]
        else:
            self.tree[ln] += [word]

    def search(self, word: str) -> bool:
        tmp = {i: j for i, j in enumerate(word) if j != '.'}
        ln = len(word)
        if ln not in self.tree:
            return False
        for strs in self.tree[ln]:
            for i, j in tmp.items():
                if strs[i] != j:
                    break
            else:
                return True
        return False

欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。

有喜欢力扣刷题的小伙伴可以加我微信（King_Uranus）互相鼓励，共同进步，一起玩转超级码力！

我的个人博客：https://qingfengpython.cn

力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown