``` 原题： 211. Add and Search Word - Data structure design Design a data structure that supports the following two operations: void addWord(word) bool search(word) search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter. Example: addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b..") -> true Note: You may assume that all words are consist of lowercase letters a-z. 总结：栈 stack 的利用，先进后出的作用，可以保持 链表一类的数据的连贯操作，可以用来替代广度搜索。 每一层次可以用进栈出栈进行替代。 stack=[（node,str）],形式的数据结构，有记忆状态的作用。 应用： 字符串的遍历，广度搜索。 import collections class WordNode: def __init__(self): self.children = {} self.isEnd = False class WordDictionary: def __init__(self): self.root = WordNode() def addWord(self, word): cur_node=self.root for char_iter in word: if char_iter in cur_node.children: cur_node=cur_node.children[char_iter] else: new_node=WordNode() cur_node.children[char_iter]=new_node cur_node=new_node # cur_node=cur_node.children[char_iter] cur_node.isEnd=True def search(self, word): stack=[(self.root,word)] while stack: node,w=stack.pop() if not w: if node.isEnd: return True # print([w]) elif w[0] == '.': for node_iter in node.children.values(): stack.append((node_iter,w[1:])) elif w[0] in node.children: nodes_cur=node.children[w[0]] stack.append((nodes_cur,w[1:])) else: pass return False class WordDictionary: def __init__(self): self.root = WordNode() def addWord(self, word): node = self.root for w in word: if w in node.children: node = node.children[w] else: node.children[w] = WordNode() node = node.children[w] node.isEnd = True def search(self, word): stack = [(self.root, word)] while stack: node, w = stack.pop() if not w: if node.isEnd: return True elif w[0] == '.': for n in node.children.values(): stack.append((n, w[1:])) else: if w[0] in node.children: n = node.children[w[0]] stack.append((n, w[1:])) return False if __name__=='__main__': wd=WordDictionary() # wd.addWord("bad") # wd.addWord("dad") # wd.addWord("mad") # out=wd.search("pad") # print(out) # out =wd.search("bad") # print(out) # out =wd.search(".ad") # print(out) # out =wd.search("b..") # print(out) words=["WordDictionary", "addWord", "addWord", "search", "search", "search", "search", "search", "search"] detect_words=[ ["a"], ["a"], ["."], ["a"], ["aa"], ["a"], [".a"], ["a."]] for word in words: wd.addWord(word) for detect_word in detect_words: out=wd.search(detect_word[0]) print(out) ```