高效的英文单词前缀匹配

题目如下

• 有一个英文单词库（数组），里面有几十万个英文单词
• 输入一个字符串，快速判断是不是某一个单词的前缀

思路如下

• 常规思路

  1. 遍历单词库数组
  2. indexOf判断前缀
  3. 实际时间复杂度超过了O(n) 因为要考虑indexOf 的计算量

• 优化

  • 英文字母一共26个，可以提前把单词库数组拆分成为26个
  • 既然第一层拆分为26个，第二层、第三层，还可以继续分
  • 最后把单词库拆分为一棵树

性能分析

• 如遍历数组，时间复杂度至少O(n)起步（n是数组长度）
• 而改为树，时间复杂度降低到O(m)（m是单词长度）
• PS：哈希表（对象）通过key查询，时间复杂度是O(1)