我一直在思考游戏中使用的算法Ruzzle一阵子。游戏的目的是在给定的网格中找到任何单词的存在，单词可以在上下、上下、左右、左右、上下对角线等任何方向上匹配。
让我们简单点。在具有相同匹配约束(方向)的二维网格中查找给定单词。时间复杂度最高的算法是什么？
例如，可以在这个网格中找到 FOREVER。
H O F E R
L R E T O
S N V O R
P Q T E N
最佳答案
您可以使用 Trie 进一步优化它数据结构。一旦你用所有的英语单词(或不同的语言)填充了结构，你就可以在 O(1) 中检查是否需要探索特定的相邻字符。
请注意，此时您正在用存储换取时间:您可能需要更多的 RAM 来存储整个 Trie，但查询它的速度要比检查有序的单词列表快。
就游戏背后的架构而言，我认为他们使用专用服务器，该服务器全天候在数据库中存储新游戏(矩阵)及其允许单词列表。在游戏过程中，您的设备会收到一个 ID，它会下载矩阵和允许的单词列表，这足以让您玩游戏。在每场比赛结束时，所有内容都会被删除，最终分数(只是一个整数)会提交给服务器，服务器会更新您的个人资料。在实际游戏中还有更多东西，因为它们也有徽章和统计数据(但收集这些东西是微不足道的)。请记住，这正是我设计和开发它的方式。
你怎么看？我们可以做得更好吗？
关于游戏 Ruzzle 中使用的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19659489/