本文主要是介绍leetcode211. 添加与搜索单词 - 数据结构设计,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
设计一个支持以下两种操作的数据结构:
void addWord(word)
bool search(word)
search(word) 可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。
参考leetcode208. 实现 Trie (前缀树):
class WordDictionary:def __init__(self):"""Initialize your data structure here."""self.trie = {}def addWord(self, word: str) -> None:"""Adds a word into the data structure."""node = self.triefor c in word:node = node.setdefault(c, {})node['end'] = 1def 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.helper(word, self.trie)def helper(self, word, root):if not word:return root.get('end', 0) == 1if not root:return Falsenode = rootfor c in word:if c != '.':if c not in node:return Falsereturn self.helper(word[1:], node[c])else:for k, v in node.items():if k != 'end' and self.helper(word[1:], node[k]):return Truereturn False
这篇关于leetcode211. 添加与搜索单词 - 数据结构设计的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!