wint搜索单词
字符串前缀匹配
题目
请描述算法思路，不要求写出代码。
- 先给一个英文单词库（数组），里面有几十万个英文单词
- 再给一个输入框，输入字母，搜索单词
- 输入英文字母，要实时给出搜索结果，按前缀匹配
要求
- 尽量快
- 不要使用防抖（输入过程中就及时识别）
常规思路
keyup 之后，拿当前的单词，遍历词库数组，通过 indexOf 来前缀匹配。
性能分析
- 算法思路的时间复杂度是
O(n) - 外加
indexOf也需要时间复杂度。实际的复杂度要超过O(n)
优化数据结构
英文字母一共 26 个，可按照第一个字母分组，分为 26 组。这样搜索次数就减少很多。
可按照第一个字母分组，那也可以按照第二个、第三个字母分组。
即，在程序初始化时，把数组变成一个树，然后按照字母顺序在树中查找。
js
const arr = [
'abs',
'arab',
'array',
'arrow',
'boot',
'boss',
// 更多...
]
const obj = {
a: {
b: {
s: {}
},
r: {
a: {
b: {}
},
r: {
a: {
y: {}
},
o: {
w: {}
}
}
}
},
b: {
o: {
o: {
t: {}
},
s: {
s: {}
}
}
},
// 更多...
}
这样时间复杂度就大幅度减少，从 O(n) 降低到 O(m) （m 是单词的最大长度）
划重点
- 对于已经明确的范围的数据，可以考虑使用哈希表
- 以空间换时间