字典树，即 Trie 树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串。
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
Trie树的具体模板如下：
# Python
class Trie(object):
def __init__(self):
self.root = {}
self.end_of_word = "#"
def insert(self, word):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.end_of_word] = self.end_of_word
def search(self, word):
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.end_of_word in node
def startsWith(self, prefix):
node = self.root
for char in prefix:
if char not in node:
return False
node = node[char]
return True并查集的代码实现如下：
# Python
def init(p):
# for i = 0 .. n: p[i] = i;
p = [i for i in range(n)]
def union(self, p, i, j):
p1 = self.parent(p, i)
p2 = self.parent(p, j)
p[p1] = p2
def parent(self, p, i):
root = i
while p[root] != root:
root = p[root]
while p[i] != i: # 路径压缩 ?
x = i; i = p[i]; p[x] = root
return root