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

Question

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

Спасибо всем

Answer 1

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

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

Answer 2

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

aardvark:aaadkrr
albatross:aablorsst

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

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

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

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

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

Пока мой grepрешение на основе моих задач отлично подойдет, вы, вероятно, не хотите полагаться на внешние инструменты и подпроцессы в надежном приложении.