Формируем слово из зашифрованных букв в java

Question

я делаю игровой проект, в котором мы должны динамически формировать слова с заданным набором букв ... данный набор букв может содержать также дубликаты ... при формировании слов мы можем использовать букву из заданногонабор букв для любого количества раз (скажем, дважды или трижды) ... помогите мне с алгоритмом, чтобы сформировать все возможные значащие слова из данного набора

Спасибо всем

Answer 1

Я сделал нечто похожее для решения кроссвордов много лун назад. Я в основном взял файл словаря и изменил его так, чтобы он выглядел так:

aardvark:aaadkrr
albatross:aablorsst

Тогда для заданного набора букв я мог бы просто отсортировать их и использовать что-то вроде:

grep ':{sorted letters}$' mywords.txt | sed 's/:.*$//'

и это дало бы мне слова-кандидаты.

Вам придётся обернуть код перестановки / комбинации, если вы ищете слова, которые могут использовать меньше, чем полный набор, но приведенный алгоритм был очень эффективным.

Для Java я бы рассмотрел либо сохранение хеш-таблицы в памяти (при условии, что у вас есть место), либо использование внешней базы данных, где ключи поиска являются отсортированными вариациями, что, конечно, допускает дублирование, поскольку pore и rope оба пришли бы из eorp.

Хотя мое решение на основе grep было вполне подходящим для моих собственных целей, вы, вероятно, не хотите полагаться на внешние инструменты и подпроцессы в надежном приложении.

Answer 2

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

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