第99题 高效的字符串前缀匹配如何做

• 有一个英文单词库（数组），里面有几十个英文单词
• 输入一个字符串，快速判断是不是某一个单词的前缀
• 说明思路，不用写代码

思路分析

• 常规思路
  • 遍历单词库数组
  • indexOf判断前缀
  • 实际复杂度超过了O(n)，因为每一步遍历要考虑indexOf的计算量
• 优化
  • 英文字母一共26个，可以提前把单词库数组拆分为26个
  • 第一层拆分为26个，第二第三层也可以继续拆分
  • 最后把单词库拆分为一颗树
  • 如array拆分为{a:{r:{r:{a:{y:{}}}}}} 查询的时候这样查obj.a.r.r.a.y 时间复杂度就是O(1)
  • 转为为树的过程我们不用管，单词库更新频率一般都是很低的，我们执行一次提前转换好，通过哈希表（对象）查询key非常快
• 性能分析
  • 如遍历数组，时间复杂度至少O(n)起步（n是数组长度）
  • 改为树，时间复杂度从大于O(n)降低到O(m)（m是单词的长度）
  • 哈希表（对象）通过key查询，时间复杂度是O(1)