字典树trie

基础知识

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

• 多数情况下可以通过用一个set来记录所有单词的prefix来替代，时间复杂度不变，空间复杂度略高

• 确定有限状态自动机

• 可以解决多个string查询prefix/suffix，如588， 1268， 745

• trie+dfs结合解决字典题如 139，140