这节课讲了两种数据结构，Trie和并查集。并查集的作用在不考虑顺序，只考虑集合的情况，可以增加边，不可以减少边的情况。find和union的操作都是O(1)， Trie可以实现查询prefix和word，查询prefix是hashtable无法做到的。
并查集的模板
def union(self, a, b):
f1 = self.find(a)
f2 = self.find(b)
if f1 != f2:
self.m[f2] = f1
def find(self, n):
if n == self.m[n]:
return n
self.m[n] = self.find(self.m[n])
return self.m[n]
Trie的模板
class TrieNode:
def __init__(self, c):
self.c = c
self.stop = False
self.children = {}
class Trie:
def __init__(self):
self.root = TrieNode("")
def insert(self, word):
node = self.root
for c in word:
if c not in node.children:
node.children[c] = TrieNode(c)
node = node.children[c]
node.stop = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.stop
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return False
node = node.children[c]
return True
Number of Islands: 其实这道题用bfs，dfs和并查集都可以做。并查集的做法是先把如果某个元素的左或上有1元素的话，就做一次union，然后再数数有多少个boss
Connecting Graph：很直观的并查集，找到自己的boss，只是union的时候要注意顺序，把小一些的值做为union的father节点。
Connecting Graph II：和上一题类似，加一个size dict来记录每个boss的size就可以了
Connecting Graph III：和上一题类似，加一个全局count在union的时候不停的递减
Graph Valid Tree： 利用上一题的记录count的想法，valid tree要满足，所有节点都有一个boss，任何两个节点在做union之前不能有同一个boss（否则就会形成环）
Add and Search Word: 在search的时候用一个递归来做，其它都类似模板
Implement Trie： 见Trie模板
Find the Weak Connected Component in the Directed Graph：直接用并查集就可以了
Connected Component in Undirected Graph： 和上一题解法一模一样
Number of Islands II： 盘古开天地的操作，和第一题很类似，只是要搜索上下左右四个方向，并且把新出现的岛屿做为boss
Word search: 这题可以用backtracking来做
Word search II: 直接loop words再对每一个word用上面的解法就过不了了，TLE。 可以把words先变为Trie，然后针对Trie在进行backtracking，这样会减少运行时间。
Surrounded Regions: 类似第一题，只是要把边界上的0和其它地方的0区别对待（设为不同的boss），其实这题用bfs或者dfs应该很好做
Word Squares： 利用Trie来找到拥有某一个prefix的所有words，实现这样的操作就容易多了。
