Алгоритм JavaScript для сопоставления слов в словаре

Question

У меня есть массив, который содержит несколько тысяч слов.У меня есть поле ввода на моей веб-странице, которое позволяет пользователю ввести пару букв, а затем нажать кнопку поиска.Когда пользователь нажимает кнопку поиска, приложение должно заглянуть в словарь и посмотреть, какие слова могут быть образованы из предоставленных букв.Каждую букву можно использовать только один раз (как в скрэббл).

Уже есть библиотека поиска для выполнения чего-то подобного?Я не хочу изобретать велосипед, если не нужно.Если нет, есть ли у кого-нибудь идеи для высокопроизводительного решения.Я предполагаю, что это было сделано миллионы раз раньше.

Answer 1

Что вам нужно сделать, это преобразовать массив слов в хеш-таблицу, где ключом являются отсортированные буквы каждого слова. Пример:

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

Затем вы берете письма пользователя, сортируете их и создаете хеш-таблицу (любой словарь подразумевает это, но хеш-таблицы наиболее эффективны в этом случае), используя отсортированные буквы в качестве ключа. Список, соответствующий вашему ключу, является списком слов, которые вы можете сделать с этими буквами. Преимущество состоит в том, что временная сложность O (n) = 1.

Answer 2

Стив Ханов тоже кое-что написал по этому поводу:

http://stevehanov.ca/blog/index.php?id=120

Answer 3

Джон Резиг из JQuery слава тоже думал об этой проблеме:

http://ejohn.org/blog/dictionary-lookups-in-javascript/