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

Question

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

Тебе дали:

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

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

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

Answer 1

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