编码面试的备忘单

原文：https://www.techinterviewhandbook.org/algorithms/trie/

简介

尝试是特殊的树(前缀树)，使搜索和存储字符串更有效。尝试有许多实际应用，比如进行搜索和提供自动完成。了解这些常见的应用程序是很有帮助的，这样您就可以很容易地确定何时可以使用 trie 有效地解决问题。

熟悉从零开始实现，一个Trie类及其add、remove和search方法。

学习资源

读物
- 试图理解尝试，basecs
- 实现 Trie(前缀树)，LeetCode
附加(仅当您有时间时)
- 压缩基数树而没有(太多)撕裂，basecs

时间复杂度

m是操作中使用的字符串的长度。

操作	大 O	注意
搜索	O(m)
插入	O(m)
去除	O(m)

拐角情况

在空的 trie 中搜索字符串
将空字符串插入到 trie 中

技巧

有时，将单词字典(在列表中给出)预处理成 trie，将提高在 n 个单词中搜索长度为 k 的单词的效率。搜索变成 O(k)而不是 O(n)。

基本问题

如果你在学习这个话题，这些是需要练习的基本问题。

实现 Trie(前缀树)

推荐课程

AlgoMonster T3】

AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得终身访问。 今天加入七折优惠→

寻找编码面试:编码问题的模式

设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式，而不是背答案！ 现在获得终身使用权→