Python：在字符矩阵中查找单词

Question

我正在尝试创建一个文字游戏，包括在一个5x5个字符的矩阵中查找单词，如下所示：

[['a', 'a', 'u', 'r', 'a'],
 ['m', 'v', 'g', 'n', 'x'],
 ['a', 'q', 'h', 'y', 'o'],
 ['p', 'r', 'h', 'l', 'h'],
 ['v', 'h', 'y', 'o', 'j']]

我已经把它列为一个列表。”应该找到“木棉”，而不是“尼龙”，因为它重复使用了“n”。我发现了一个类似的问题here，但我不知道C

我目前的解决方案是为单词中的每个字母创建一个字典，它由一系列元组组成，这些元组在黑板上的位置如下：{'letter'：[（row，column），（row，column）]}。然后，对于单词中的每个字母，我检查它在板上的每个位置是否与前一个字母的位置兼容。如果是，我将该位置添加到新的路径字典。在

不过，对于重复字母和其他情况，比如“尼龙”这样的情况，这种方法是失败的。它已经相当庞大和混乱，我应该重新开始。有没有更简洁的解决方案？
编辑：

澄清：如果存在一条连接网格中单词中每个字母的路径，那么单词就是“在”网格中。上、下、左、右和对角线都是允许的x'与'y'相邻，y与'l'相邻，依此类推。路径需要没有特定的形状，只要每个字母是相邻的，并且板上没有特定的字母被使用两次。一个单词可以有重复的字母，所以“pama”是允许的，因为可以使用多个A。在

@MSW是对的，游戏是boggle，虽然我是第一次发现这个！在

Answer 1

如果您想检查单词的成员资格，那么将字母映射到位置的字典的起点是一个不错的起点：

letter_positions = {}
for (y, row) in enumerate(board):
    for (x, letter) in enumerate(row):
         letter_positions.setdefault(letter, []).append((x, y))

在此基础上，您的函数应该跟踪哪些字母已经被使用，以确保不会重复它们：

^{pr2}$

例如：

>>> find_word("xylon")
[(4, 1), (3, 2), (3, 3), (4, 2), (3, 1)]
>>> find_word("bad")
None

现在，注意这里的运行时是O(not great)，因为position in used（used是一个列表，需要对每个字母位置进行O(N)搜索）和used + [position]和{}（每一个都将导致一个分配+复制）。在实践中，这将是~O(word length ^ 2)，但可以通过一些更合理的数据结构将其改进为~O(word length)。在