Сублинейный Jotto решатель (алгоритм)

Question

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

Вам даны:

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

Найдите правильное слово с теми же символами, что и секретное слово.Опять же, все слова имеют длину 5. Все слова имеют уникальные символы.

Я изо всех сил пытаюсь найти сублинейное решение.У кого-нибудь есть подсказка?

Answer 1

Если вы можете выполнить предварительную обработку в автономном режиме, вы можете построить BK-дерево для слов в словаре, используя симметричную разностную метрику (т. Е. D (A, B) = | A - B | + |B - A |, что будет пять минус значение функции).Затем вы можете использовать функцию для обхода BK-дерева очевидным образом.