JavaScript 算法来匹配字典中的单词
我有一个包含几千个单词的数组。我的网页上有一个输入字段，允许用户输入几个字母，然后单击搜索。当用户点击搜索时，应用程序应该在字典中查找，看看可以用提供的字母组成哪些单词。每个字母只能使用一次（就像拼字游戏一样）。
是否已经有一个搜索库可以做这样的事情？如果没有必要，我不想重新发明轮子。如果没有，是否有人有高性能解决方案的想法。我想这之前已经被做过数百万次了。
I have an array that contains a few thousand words. I have an input field on my webpage that allows a user to enter in a couple of letters, and then hit search. When the user hits search, the application should look in the dictionary and see what words can be formed off of the supplied letters. Each letter can be used only once ( like in scrabble ).
Is there already a search library for doing something like this? I don't want to reinvent the wheel if not necessary. If not, does anyone have ideas for a high performance solution. I'd imagine this has been done millions of times before.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
jQuery 名人 John Resig 也一直在思考这个问题：
http://ejohn。 org/blog/dictionary-lookups-in-javascript/
John Resig of jQuery fame has been thinking about this problem as well:
http://ejohn.org/blog/dictionary-lookups-in-javascript/
Steve Hanov 也写了一些关于此的内容：
http://stevehanov.ca/blog/index.php ?id=120
Steve Hanov wrote something about this too:
http://stevehanov.ca/blog/index.php?id=120
您需要做的是将单词数组转换为哈希表，其中键是每个单词的字母排序。例如：
然后你获取用户的字母，对它们进行排序，然后使用排序后的字母作为键进行哈希表（任何字典实现都可以，但哈希表在这种情况下是最有效的）查找。与您的键对应的列表是您可以用这些字母执行的单词列表。这样做的优点是时间复杂度为 O(n) = 1。
What you need to do is convert the array of words in a hashtable where the key is each word's letters sorted. Ex:
Then you take the user's letters, you sort them, and you do a hashtable (any dictionary impl would do, but hashtables are most efficient in this case) lookup using the sorted letters as key. The list corresponding to your key is the list of words you can do with those letters. This has the advantage of having a time complexity of O(n) = 1.