javascript - 用于匹配字典中单词的 JavaScript 算法

Question

我有一个包含几千个单词的数组。我的网页上有一个输入字段，允许用户输入几个字母，然后点击搜索。当用户点击搜索时，应用程序应该查看字典并查看可以从提供的字母中形成哪些单词。每个字母只能使用一次（如在 scrabble 中）。

是否已经有一个搜索库可以做这样的事情？如果没有必要，我不想重新发明轮子。如果没有，是否有人对高性能解决方案有想法。我想这在以前已经做过数百万次了。

score 1 · Accepted Answer

史蒂夫哈诺夫也写了一些关于这个的东西：

score 1 · Accepted Answer

您需要做的是转换哈希表中的单词数组，其中键是每个单词的字母排序。前任：

['car', 'shoe', 'train']
=> {'acr': ['car'],
     'ehos': ['shoe'],
     'ainrt': ['train']}

然后获取用户的字母，对它们进行排序，然后使用排序后的字母作为键进行哈希表（任何字典 impl 都可以，但哈希表在这种情况下最有效）查找。与您的键对应的列表是您可以使用这些字母执行的单词列表。这具有时间复杂度为 O(n) = 1 的优点。

score 1 · Accepted Answer

jQuery 成名的 John Resig 也一直在思考这个问题：

3 回答 3