Trie

1.定义

一个用空间换时间的多叉树

2.目标

• 处理字符串，高效搜索，时间复杂度和字符串的长度相关O(m)
• 寻找前缀，搜索提示

缺点

• 空间有限

已知n层k叉节点总数：(k^n-1)/(k-1)，那么trie空间复杂度是O(k^n)，如果k=26，字符串长度n=10，算一算

>>> 26 ** 10
141167095653376

是不是超厉害？！

优化： Compressed trie, ternary search trie

3.基本操作

就链表一样的add, contains，优化没看

code

https://github.com/nyannko/leetcode-java/blob/master/src/ds/trie/Trie.java