面试150 添加与搜索单词--数据结构设计

思路

通过哈希法去实现，这里主要描述search的思路：如果’.‘不在word中，我们只需要去查询word在不在set中。如果’.‘存在，我们对哈希中的字符串进行遍历w，如果当前字符串的长度不等于word跳过,对word进行遍历，比较word的每一个元素与w的每一个元素，如果word[i]不等于’.'并且不等于w[i]，则说明不匹配，最后return False。

class WordDictionary:def __init__(self):self.d=set()def addWord(self, word: str) -> None:self.d.add(word)def search(self, word: str) -> bool:if '.' not in word:return word in self.d for w in self.d:if len(w)!=len(word):continuematch=Truefor i in range(len(word)):if word[i]!='.' and word[i]!=w[i]:match=Falsebreakif match:return True return False# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)