c++ - 给定字典和字母查找最长的单词

Question

对于我正在开发的单词构建游戏，我有一个 trie 树来存储字典中的每个可能的单词。目前大约有 179,000。

根据游戏的运行方式，有一个 5x5(或将来可能更大，具体取决于该问题的解决方案的效率)的字母网格。玩家和 PC 轮流从这些字母中拼出单词，根据字母和单词的长度获得分数(字母估值类似于拼字游戏，但这并不重要)。每当玩家说出一个单词时，这些字母就会从棋盘上移除，一直持续到无法说出任何单词为止，此时网格将重置(该回合的获胜者将获得奖励)。

问题是这样的:给定一个 5x5 的字母网格和那个字典特里树，我如何才能有效地确定可以组成的最长单词或所有可能单词的列表？请注意，字母不需要相互接触即可使用；网格的任何字母都可以。

我能想到的唯一方法是基本上在 trie 上做一个 BFS，当下一个字母不在网格中时修剪它，但这对我来说似乎不是很有效，因为它必须尝试对于网格中的每个字母。有更好的方法吗？

Answer 1

找到“最佳”单词总是需要在 trie 中进行一些搜索。但是 trie 并不是一个糟糕的结构。

但是，您必须执行以下操作:

1. 从你的董事会中挑选一封信。
2. 在 trie 中找到当前“单词”的节点。
3. 在黑板上选择另一个字母。
4. 从第 2 步开始重复，直到:找不到单词或黑板上没有字母。
5. 记住您找到的单词的“分数”。
6. 对板上所有(唯一的？)起始字母重复此过程。

您可能想检查您是否“以前尝试过此序列”，但我不确定这是否有很大好处。

为了使与计算机竞争的竞争对手相当公平，您可能需要限制计算机的尝试次数，因为在这种情况下人类可能永远无法战胜计算机。