algorithm - 次线性 Jotto 求解器(算法)

Question

我正在尝试实现 Jotto 求解器。 Here是对 Jotto 游戏的描述(只读开头)。这是我要解决的问题:

你得到:

• 有效英语单词的字典(长度均为 5 且具有唯一字符)
• 要猜的 secret 单词，由 5 个不同的字符组成(字典中存在)
• 一个函数，返回您猜测的单词和 secret 单词之间交集的大小(共同字符数)。

找到一个与 secret 词具有相同字符的有效词。同样，所有单词的长度都是 5。所有单词都有唯一的字符。

我正在努力寻找次线性解决方案。有人知道吗？

Answer 1

如果你可以离线预处理，你可以构建一个BK-tree使用对称差异度量(即 d(A, B) = |A - B| + |B - A|，将是 5 减去函数值)对字典中的单词进行计算。然后你就可以使用这个函数以显而易见的方式遍历BK-tree了。