题目地址(211. 添加与搜索单词 - 数据结构设计)
https://leetcode-cn.com/problems/add-and-search-word-data-structure-design/description/
题目描述
设计一个支持以下两种操作的数据结构:
void addWord(word)
bool search(word)
search(word) 可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
示例:
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
说明:
你可以假设所有单词都是由小写字母 a-z 组成的。
思路
我们首先不考虑字符"."的情况。这种情况比较简单,我们 addWord 直接添加到数组尾部,search 则线性查找即可。
接下来我们考虑特殊字符“.”,其实也不难,只不过 search 的时候,判断如果是“.”, 我们认为匹配到了,继续往后匹配即可。
上面的代码复杂度会比较高,我们考虑优化。如果你熟悉前缀树的话,应该注意到这可以使用前缀树来进行优化。前缀树优化之后每次查找复杂度是$O(h)$, 其中 h 是前缀树深度,也就是最长的字符串长度。
关于前缀树,LeetCode 有很多题目。有的是直接考察,让你实现一个前缀树,有的是间接考察,比如本题。前缀树代码见下方,大家之后可以直接当成前缀树的解题模板使用。
由于我们这道题需要考虑特殊字符".",因此我们需要对标准前缀树做一点改造,insert 不做改变,我们只需要改变 search 即可,代码(Python 3):
def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curr = self.Trie for i, w in enumerate(word): if w == '.': wizards = [] for k in curr.keys(): if k == '#': continue wizards.append(self.search(word[:i] + k + word[i + 1:])) return any(wizards) if w not in curr: return False curr = curr[w] return "#" in curr
标准的前缀树搜索我也贴一下代码,大家可以对比一下:
def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curr = self.Trie for w in word: if w not in curr: return False curr = curr[w] return "#" in curr
关键点
- 前缀树(也叫字典树),英文名 Trie(读作 tree 或者 try)
代码
- 语言支持:Python3
Python3 Code:
关于 Trie 的代码:
class Trie: def __init__(self): """ Initialize your data structure here. """ self.Trie = {} def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ curr = self.Trie for w in word: if w not in curr: curr[w] = {} curr = curr[w] curr['#'] = 1 def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ curr = self.Trie for i, w in enumerate(word): if w == '.': wizards = [] for k in curr.keys(): if k == '#': continue wizards.append(self.search(word[:i] + k + word[i + 1:])) return any(wizards) if w not in curr: return False curr = curr[w] return "#" in curr
主逻辑代码:
class WordDictionary: def __init__(self): """ Initialize your data structure here. """ self.trie = Trie() def addWord(self, word: str) -> None: """ Adds a word into the data structure. """ self.trie.insert(word) def search(self, word: str) -> bool: """ Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. """ return self.trie.search(word) # Your WordDictionary object will be instantiated and called as such: # obj = WordDictionary() # obj.addWord(word) # param_2 = obj.search(word)
相关题目
- 208.implement-trie-prefix-tree
- 212.word-search-ii
Design and implement a TwoSum class. It should support the following operations: add and find.add - Add the number to an internal data structure.find - Find if there exists any pai…
LeetCode题解139.word-break题目地址 https://leetcode.com/problems/word-break/description/ 题目描述 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be seg…
LeetCode题解201.bitwise-and-of-numbers-range题目地址 https://leetcode.com/problems/bitwise-and-of-numbers-range/description/ 题目描述 Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbe…
LeetCode题解121.best-time-to-buy-and-sell-stock题目地址 https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/ 题目描述 Say you have an array for which the ith element is the price of a given stock on day i. If you …
LeetCode题解122.best-time-to-buy-and-sell-stock-ii题目地址 https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/ 题目描述 Say you have an array for which the ith element is the price of a given stock on day i. Desi…