arrays - 检查电话号码中单词集合的最快算法

例如，我有一个数组[“bab”，“col”，“stro”]…

IN     OUT
222    bab
7876   stro
999    <empty>        no match

有没有比o（n^2）更好的算法来解决这个问题？

最佳答案

将列表预处理为一个翻译表，并将每个单词的关键字设置为其数字等价项。这使您可以轻松查找搜索结果。

dial_num = [
    'a' : 2,
    'b' : 2,
    'c' : 2.
    'd' : 3,
    ...
]

接下来，翻译你的每一个单词：

dial_word = [
    222 : 'bab',
    264 : 'col',
    7876 : 'stro'
    ...
]

该任务在数组长度（字符）上为o（n）。
现在，您可以对给定的数字进行简单的搜索（线性或对数）。如果您想进一步将dial_word预处理为哈希表，那么您将进行O（1）查找。