所有題解方法請移步 github-Leecode_summary
Tire
概念： 計算機科學中旗国，Tire-Tree又稱前綴樹或字典樹褐望，是一種有序樹裸影，用于存儲字符串挣轨。
特點： 邊保存字符，結點表示依次經(jīng)過所有邊的字符串轩猩，下為保存四個鍵的tire結構(adv, b, cpdd, cd)卷扮。
應用： 常用于搜索提示，比如在瀏覽器搜索框輸入網(wǎng)址均践，匹配最相似的結果晤锹、IP路由(最長匹配前綴)、
Tire示意圖
211. 添加與搜索單詞 - 數(shù)據(jù)結構設計
剛開始寫的時候是對set中每一個word遍歷匹配彤委，結果超時鞭铆，改進之后用長度字典，176ms葫慎，開心衔彻，但看答案好像主要是用Tree的思想做的hh，果然菜的很真實...
Tips-1: all() any()
奇怪偷办，以前從沒有看到過all()和any()艰额，今天看題解是第一次了解，怎么說椒涯，寫寫吧：
# all() 函數(shù)用于判斷給定可迭代參數(shù)中所有元素是否都為True柄沮，是則返回True
>>> all([1, 2, 3, 4]) # 0 False '' None 屬于False類
True
# any() 函數(shù)用于判斷給定可迭代參數(shù)中所有元素是否都為False，是則返回False
>>> any([0, 1, 2, 3])
True
Tips-2: setdefault defaultdict
-
dict.setdefault (key, default=None)：和get()方法類似废岂，返回字典中的 key 對應的值
如果 dict 包含給定 key祖搓，返回該鍵對應的值
如果 dict 不包含給定key，將添加減并設置鍵值為默認值湖苞，并返回
>>> dic = {}
>>> dic.setdefault('a', 1)
1
>>> dic = {}
>>> li = [1, 2, 3, 4]
>>> for i in li:
... dic.setdefault('a', []).append(i)
...
>>> dic
{'a': [1, 2, 3, 4]}
-
defaultdict()是 collections 模塊下dict子類拯欧，接收一個工廠函數(shù)(list, dict, set, str) 作為參數(shù)
>>> from collections import defaultdict
>>> dic = defaultdict(set)
>>> li = [1, 2, 3, 4, 3]
>>> for i in li:
... dic['a'].add(i)
...
>>> dic
defaultdict(<class 'set'>, {'a': {1, 2, 3, 4}})
但其實在Tire中用setdefault時反而是比較合理的，因為并不需要 add/append sth
208.實現(xiàn)前綴樹
搬運工：python 實現(xiàn) trie(字典) 樹
或者直接看github-Tire篇 208 題答案就好
212. 單詞搜索II （又陷入了超時的煩惱...
看完答案有兩點總結：（超時代碼也放在了github财骨，畢竟辛苦寫的
- 我做題的時候是以
board為主體去做的镐作，構建board的前綴樹，因為board是m*n矩陣隆箩，所以如果完全遍歷整個矩陣该贾，這個tire將非常大且多余，沒想到題解是以構建words tire為主體做的捌臊，哎杨蛋，怎么腦子就不會轉(zhuǎn)彎呢？理澎？逞力？ - marked 使用了 deepcopy()，這也是超時的關鍵
