LC吐血整理之Trie篇

所有题解方法请移步 github-Leecode_summary

Tire

概念： 计算机科学中，Tire-Tree又称前缀树或字典树，是一种有序树，用于存储字符串。
特点： 边保存字符，结点表示依次经过所有边的字符串，下为保存四个键的tire结构(adv, b, cpdd, cd)。
应用： 常用于搜索提示，比如在浏览器搜索框输入网址，匹配最相似的结果、IP路由(最长匹配前缀)、

Tire示意图

211. 添加与搜索单词 - 数据结构设计

刚开始写的时候是对set中每一个word遍历匹配，结果超时，改进之后用长度字典，176ms，开心，但看答案好像主要是用Tree的思想做的hh，果然菜的很真实...
Tips-1: all() any()
奇怪，以前从没有看到过all()和any()，今天看题解是第一次了解，怎么说，写写吧：

#  all() 函数用于判断给定可迭代参数中所有元素是否都为True，是则返回True
>>> all([1, 2, 3, 4])   # 0 False '' None 属于False类
True
# any() 函数用于判断给定可迭代参数中所有元素是否都为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子类，接收一个工厂函数(list, dict, set, str) 作为参数

>>> 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.实现前缀树

搬运工：python 实现 trie(字典) 树
或者直接看github-Tire篇 208 题答案就好

212. 单词搜索II （又陷入了超时的烦恼...

看完答案有两点总结：（超时代码也放在了github，毕竟辛苦写的

• 我做题的时候是以 board 为主体去做的，构建 board 的前缀树，因为 board 是m*n矩阵，所以如果完全遍历整个矩阵，这个tire将非常大且多余，没想到题解是以构建words tire为主体做的，哎，怎么脑子就不会转弯呢？？？
• marked 使用了 deepcopy()，这也是超时的关键