字典树trie

基础知识

• 一个树形结构，一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题

• 多数情况下可以通过用一个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中的键是无序的，因此不适合按字典序排序字符串。