TRIE(前缀树/字典树)
TRIE常用于存储和表示字符串的集合，并实现该集合上的增删字符串运算。其核心思想是用公共前缀表示字符串，比如abcd与abc的公共前缀是abc，当字符串间恰好没有公共前缀时，比如abc,edfg,czx构成的集合，那么其会存储3个前缀abc,edfg,czx。
其常用于存储字符串构成的集合。其结构是这样的，Trie的根节点不存储字符，其他节点仅存储单个字符，且同一层节点无重复字符。节点有变量存储“颜色”，若某节点被“染色”说明从根到该节点的路径存储了一个字符串，除此之外Trie的叶节点肯定是“染色”的。下面讨论Trie的运算结构：
1）插入：首先查找根节点全部孩子节点，若找到待插入串首字符则进入该节点并重复该步骤，若没有则在该处新建节点并插入剩余字符，最终为叶节点染色。如果用哈希表/dict来记录每个节点的儿子，可以在\(O(1)\)时间完成当前层的查找，所以可以认为时间复杂度为字符数\(O(n)\)。
2）遍历：首先想到利用节点遍历来实现，如果在节点遍历的同时记录了当前的途径路径，那只要在节点被遍历时判断当前节点是否被“染色”即可解决这个问题。可以发现这个解决方法与节点的深度优先遍历是同步进行的，所以其代价为节点数\(O(n)\)。
3）删除：首先逐个查找每个字符对应节点，直到到达待删除串尾字符的对应节点，若其是叶节点则将其删除，若其不是叶节点则取消“染色”。若未找到待删除串则返回。删除的代价是字符数\(O(n)\)。
4）查找：删除中已经讨论了查找的逻辑。
5）查找前缀：跟查找差不多。
Trie本身虽然不复杂，但其在字符串处理中的应用十分广泛，举些比较基本的例子：
1）字符串排序：这里排序是指把若干字符串，以英语字典那样的方式来排序。这可以通过规定记录子节点的序列中的元素顺序来实现，如果规定序列元素按照abcd的顺序排序，那么对这个Trie树进行上述字符串遍历即可得到排序结果。
2）字符串统计：该问题指“有一篇A个单词的文章与B个单词组成的单词表，统计单词表中各个单词在该文章的出现次数”。方法是把单词表建成Trie树，然后在Trie上查找每个单词。
3）字符串去重：把这些字符串建成Trie然后再遍历该Trie即可去重。
4）字符串前缀：Trie树可用来解决关于前缀的很多问题，例如“求多个字符串的最大公共前缀”，“求单词表中与目标单词公共前缀最长的单词”。解决第一个问题仅需把这些字符串建成Trie树，然后找出一条最长路径，这个路径的每个节点只有一个子节点。解决第二个问题同样也比较容易。
5）字符串匹配：Trie树是著名多模匹配算法“AC自动机”的基础，后面写了篇文章讨论这个。
class Node:
def __init__(self):
self.letterMap = {}
self.isEnd = False
class Trie:
def __init__(self):
self.root = Node()
@classmethod
def _traverse(cls, result, arr, node):
if node.isEnd:
result.append(''.join(arr))
for key in node.letterMap:
arr.append(key)
cls._traverse(result, arr, node.letterMap[key])
arr.pop()
def traverse(self):
result = []
self._traverse(result, [], self.root)
return result
def insert(self, word):
node = self.root
for letter in word:
if letter not in node.letterMap:
node.letterMap[letter] = Node()
node = node.letterMap[letter]
node.isEnd = True
def search(self, word):
node = self.root
letter = None
for letter in word:
if letter in node.letterMap:
node = node.letterMap[letter]
else:
return False
if letter and node.isEnd:
return True
return False
def remove(self, word):
node = self.root
parent = None
letter = None
for letter in word:
if letter in node.letterMap:
parent = node
node = node.letterMap[letter]
else:
return False
if letter and node.isEnd:
if len(node.letterMap.keys()) > 0:
node.isEnd = False
else:
parent.letterMap.pop(letter)
return True
return False
def startsWith(self, prefix):
node = self.root
for letter in prefix:
if letter in node.letterMap:
node = node.letterMap[letter]
else:
return False
return True