所有题解方法请移步 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()，这也是超时的关键
网友评论