LC吐血整理之Trie篇

Posted on | In
人生苦短 我学python

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

Tire

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

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

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

1
2
3
4
5
6
#  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，将添加减并设置键值为默认值，并返回
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    >>> 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) 作为参数
    ```Python 
    >>> 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}})

Tips-2: setdefault defaultdict
但其实在Tire中用setdefault时反而是比较合理的，因为并不需要 add/append sth

208.实现前缀树

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

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

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

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