Trie

应用

Trie树最直观的定义就是LinkedList of HashMap。所以Trie和HashMap都可以用来查询某个单词是否在字典当中。我们需要知道他们的优缺点。

Trie:

• 优点：
  • 支持字符级别的查询，比如说我们需要在matrix当中通过traverse构造单词，那么这个单词是一个一个字符形成的，我们可以在traverse的每一步去检验当前路径是否可以形成valid word。另外，对于含有regex符号的字符串，我们需要一个字符一个字符的考虑，这种情况下我们也需要通过trie去查找。
  • 节省空间，相同的prefix只存一遍，而HashMap需要存很多遍。
• 缺点：实现起来较麻烦，大部分题目使用Trie都是overkill，所以除非需要支持字符级别的查询，否则HashMap更好。

操作

三个操作：

• insert
• search
• startWith

其中insert记得把最后一个node标记为isEnd = true。其中search和startWith都可以通过同一个searchHelper helper method来实现，我们只需要return 最后一个node就可以，如果isEnd == true，那么说明找到一个完整的单词，否则至少找到了prefix。别忘了使用trie的第一步是preprocess，把字典里的所有word加入到trie树当中。

题目

• Leetcode 208. Implement Trie (Prefix Tree)
• Leetcode 212. Word Search II
• Leetcode 211. Add and Search Word - Data structure design (Facebook店面)
• Leetcode 14. Longest Common Prefix (这道题可以稍作改编，比如说string list会经常update，会经常query，那这时很明显用trie更好)