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(),这也是超时的关键
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 所有题解方法请移步 github-Leecode_summary 200. 岛屿数量 三个字:不会做,没有什么好的...
    amilyxy阅读 3,375评论 0 0
  • 所有题解方法请移步 github-Leecode_summary 133. 克隆图 DFS&BFS 有整理过对象赋...
    amilyxy阅读 3,308评论 0 0
  • 又到了踐行第三周,現對本週的班會和一周的踐行檢視做一個分享。 学习与自我提升 转型: 1)本周完成《番茄工作...
    伊伊_1049阅读 812评论 0 0
  • 最近的睡眠质量真不好,一晚上醒来三次睡不着了,不想回到那一段黑暗时期,加油努力向前奔跑!
    像风一样_不问归期阅读 482评论 0 0
  • 这周读了基思·斯坦诺维奇的这本《对“伪心理学”说不》。 在浩如烟海、良莠不齐的心理学著作面前,我们如何拨出迷雾、去...
    小天先森阅读 1,651评论 0 0