常德网站建设的策划方案,靖江网站建设价格,广东seo网站推广,信息流广告特点211. 添加与搜索单词 - 数据结构设计 题目-中等难度示例1. 题目-中等难度
请你设计一个数据结构#xff0c;支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 实现词典类 WordDictionary #xff1a; WordDictionary() 初始化词典对象void addWord(word) 将… 211. 添加与搜索单词 - 数据结构设计 题目-中等难度示例1. 题目-中等难度
请你设计一个数据结构支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 实现词典类 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 25addWord 中的 word 由小写英文字母组成search 中的 word 由 ‘.’ 或小写英文字母组成最多调用 104 次 addWord 和 search 来源力扣LeetCode 链接https://leetcode.cn/problems/summary-ranges 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
1.
时间 2808ms 击败 45.89%使用 Python3 的用户 内存 82.28MB 击败 38.51%使用 Python3 的用户
class TrieNode:def __init__(self):# 每个节点有26个可能的子节点, 对应26个英文字母self.children [None] * 26# 标记这个节点是否是当前单词的最后一个字母self.isLast Falseclass WordDictionary:def __init__(self):# 初始化时创建根节点self.li TrieNode()def addWord(self, word: str) - None:# 从根节点开始node self.li# 遍历单词中的每个字母for w in word:# 计算字母对应的索引c ord(w) - ord(a)# 如果相应的子节点不存在if not node.children[c]:# 创建新的子节点node.children[c] TrieNode()# 移动到子节点, 继续处理下一个字母node node.children[c]# 标记单词的最后一个字母node.isLast Truedef search(self, word: str) - bool:def dfs(index:int, node: TrieNode) - bool:# 如果已经检查完单词的所有字母if index len(word):# 如果是单词的结尾, 则返回 Truereturn node.isLast# 获取当前字母w word[index]# 如果当前字母不是通配符if w ! .:# 计算字母的索引c ord(w) - ord(a)# 获取相应的子节点child node.children[c]# 如果子节点存在, 递归搜索下一个字母if child is not None and dfs(index1, child):return True# 如果是通配符else:# 遍历所有可能的子节点for nc in node.children:# 如果子节点存在, 递归搜索下一个字母if nc is not None and dfs(index1,nc):# 返回True, 如果找到匹配的路径return True# 如果没有找到匹配的路径, 返回 Falsereturn False# 从根节点开始深度优先搜索return dfs(0, self.li)# Your WordDictionary object will be instantiated and called as such:
# obj WordDictionary()
# obj.addWord(word)
# param_2 obj.search(word)
