Algorithms study cheatsheets
Coding interview 的 Trie cheatsheet
Trie 学习指南，包含练习题、技巧、时间复杂度与推荐资源
Introduction
Trie 是一种特殊的 tree（prefix tree），让字符串的存储与检索更高效。Trie 在搜索和 autocomplete 等场景非常常见。熟悉这些应用场景，能让你在面试中更快判断哪些题目适合用 trie 解决。
要能从零实现一个 Trie class，包括 add、remove、search 方法。
Learning resources
- Readings
- Trying to Understand Tries, basecs
- Implement Trie (Prefix Tree), LeetCode
- Additional (only if you have time)
Time complexity
m 是操作时的字符串长度。
| Operation | Big-O |
|---|---|
| Search | O(m) |
| Insert | O(m) |
| Remove | O(m) |
Corner cases
- Searching for a string in an empty trie
- Inserting empty strings into a trie
Techniques
把一组单词（list）预处理成 trie，能让在 n 个单词里搜索长度为 k 的单词从 O(n) 降到 O(k)。
Essential questions
这些是该 topic 必练题。
Recommended practice questions
这些是在掌握基础后推荐练习的题目。