# 字典树trie

[基础知识](https://zh.wikipedia.org/wiki/Trie)

* 一个树形结构，一种专门处理**字符串匹配**的数据结构，persistent, 用来解决在**一组字符串集合中快速查找某个字符串**的问题
* 多数情况下可以通过用一个set来记录所有单词的prefix来替代，时间复杂度不变，空间复杂度略高
* 确定有限状态自动机
* 可以解决多个string查询prefix/suffix，如588， 1268， 745
* trie+dfs结合解决字典题如 139，140
* trie vs hashmap tradeoff
  * Trie非常适合前缀匹配操作, 在O(k)时间内找到以某个前缀开头的所有字符串，其中k是前缀的长度
  * 稀疏字符串集合，Trie的空间复杂度可能较高
  * Trie的插入和查找时间复杂度为O(k)，其中k是字符串的长度。对于较长的字符串，时间复杂度可能较高。
  * Trie可以用于按字典序排序字符串。
  * Hashmap的插入和查找时间复杂度为O(1)，平均情况下非常高效。
  * Hashmap不适合前缀匹配操作。要找到以某个前缀开头的所有字符串，需要遍历整个哈希表，时间复杂度为O(n)，其中n是哈希表的大小。
  * Hashmap中的键是无序的，因此不适合按字典序排序字符串。
