ios - 在不断变化的网格中寻找可能的单词

Question

我正在开发一款文字游戏，用户可以从不断变化的字母网格中创建单词。使用单词列表验证用户的选择很容易。

由于播放网格是随机生成的，并且以前播放的图 block 被删除并替换为新字母，因此我需要能够有效地检查每个用户提交之间可能的有效播放，因此如果没有可能的有效单词，我可以重置网格或其他有影响的东西。该解决方案仅需要检测当前一组图 block 中至少有一个有效的 3 - 7 个字母单词。它不需要知道所有可能的组合。用户可以从任何图 block 开始，并使用距当前所选字母任意方向的一个图 block 来构建单词。

重要提示:该解决方案不会减慢游戏速度。一旦用户提交当前单词并且新图 block 出现，他们就可以立即开始新的选择。

任何方向将不胜感激，因为到目前为止我还无法通过任何谷歌搜索找到我认为我正在寻找的东西。

使用 Swift 为 iOS8+ 构建

Answer 1

正如 @jamesp 提到的，特里树是最好的选择。你在这里有几个优势，第一个是你可以在找到一个词后摆脱困境。您不必扫描整个网格以查找所有可能的单词，只需找到一个并完成即可。从任何随机字母开始，查看它周围的字母，并将它们与特里树进行匹配。如果找到匹配项，请继续查找该匹配项周围的字母，依此类推，直到找到单词或死胡同。如果当前起始图 block 周围没有完整的单词，请继续到网格中的下一个图 block ，然后从那里再次尝试。