搜索单词

字符串前缀匹配

题目

请描述算法思路，不要求写出代码。

• 先给一个英文单词库（数组），里面有几十万个英文单词
• 再给一个输入框，输入字母，搜索单词
• 输入英文字母，要实时给出搜索结果，按前缀匹配

要求

• 尽量快
• 不要使用防抖（输入过程中就及时识别）

常规思路

keyup 之后，拿当前的单词，遍历词库数组，通过 indexOf 来前缀匹配。

性能分析

• 算法思路的时间复杂度是 O(n)
• 外加 indexOf 也需要时间复杂度。实际的复杂度要超过 O(n)

优化数据结构

英文字母一共 26 个，可按照第一个字母分组，分为 26 组。这样搜索次数就减少很多。

可按照第一个字母分组，那也可以按照第二个、第三个字母分组。
即，在程序初始化时，把数组变成一个树，然后按照字母顺序在树中查找。

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 是单词的最大长度）

划重点

• 对于已经明确的范围的数据，可以考虑使用哈希表
• 以空间换时间