Leetcode 208. 实现 Trie (前缀树)

心路历程：

一道题干进去了一个下午，单纯从解题角度可以直接用python的集合就很简单地解决（不知道是不是因为python底层的set()类）。后来从网上看到这道题应该从前缀树的角度去做，于是花了半个多小时基于字典做了前缀树的做法；后来想锻炼一下多叉树的做法，又花了一个多小时尝试。
前缀的含义是一个字符串的包含第一个元素作为开始的子序列，在代码自动补全里应用很多。

注意的点：

1、在利用字典建立多叉树的时候，一般是利用循环不变量的原则，每一层赋值root，然后判断当前层是否已经之前创建过。
2、利用class建立多叉树的时候，注意不要在初始化默认参数处设置children=[]，否则所有示例化对象的children都指向同一个内存（花了很长时间找这个bug）。
3、注意在一个单词添加完之后，结尾要跟上一个结束判断符来区分到底是一个完整的单词还是一个其他长单词的一个部分。
4、写出来bug是很正常的事情，只要按照顺序检查输入输出关系即可debug。

解法一：python原生集合

class Trie:def __init__(self):self.set = set()self.prefixset = set()def insert(self, word: str) -> None:self.set.add(word)for j in range(1, len(word)+1):  # 这块是取不到的，所以要加一，两个取不到的叠加self.prefixset.add(word[:j])def search(self, word: str) -> bool:if word in self.set:return Trueelse:return Falsedef startsWith(self, prefix: str) -> bool:# return True 直接return true可以过一半测试用例if prefix in self.prefixset:return Trueelse:return False

解法二：用字典实现多叉前缀树

class Trie:def __init__(self):  # 用字典做一个前缀树self.dict = {}self.end = "!"def insert(self, word: str) -> None:root = self.dictfor i in range(len(word)):if word[i] not in root.keys():root[word[i]] = {}  # 循环不变量root = root[word[i]]root[self.end] = Nonedef search(self, word: str) -> bool:# print(self.dict)root = self.dictfor c in word:if c in root.keys():root = root[c]else:return False# 还得保证单词结尾if self.end in root.keys():return Trueelse:return Falsedef startsWith(self, prefix: str) -> bool:root = self.dictfor c in prefix:if c in root.keys():root = root[c]else:return Falsereturn True 

解法三：利用多叉树类实现前缀树（对比起来还是用字典实现多叉树方便一些）

class TreeNode:def __init__(self, val=None):  # 不能在这里给children=[]赋值然后再self.children = children，否则所有实例都维护一个列表内存（浅拷贝问题）self.val =valself.children = []  # !!!def values(self):values = []for eve in self.children:values.append(eve.val)return valuesdef findvalindex(self, aval):for i in range(len(self.children)):if self.children[i].val == aval:return iassert Falseclass Trie:def __init__(self):  # 用多叉树作前缀树self.root = TreeNode()def insert(self, word: str) -> None:root = self.rootfor i in range(len(word)):if word[i] not in root.values():node = TreeNode(word[i])root.children.append(node)root = node  # 这句话无法赋值？？有赋值作用，并且内存也确实变了，但是不知道为什么.values()方法都赋值到了根节点上去-》因为浅拷贝到了一个列表上# print(root, root.children[-1])else:vindex = root.findvalindex(word[i])root = root.children[vindex]leaf = TreeNode('!')root.children.append(leaf)  # 加入结束符号def search(self, word: str) -> bool:root = self.rootfor c in word:if c in root.values():vindex = root.findvalindex(c)root = root.children[vindex]else:return False# print(root.values())# 此时root的children中应该包含leafif '!' in root.values():return Trueelse:return Falsedef startsWith(self, prefix: str) -> bool:root = self.rootfor c in prefix:if c in root.values():vindex = root.findvalindex(c)root = root.children[vindex]else:return Falsereturn True # 不需要是none