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']]

我将其表示为列表列表。应该找到“xylon”而不是“nylon”，因为它重复使用了“n”。我发现了类似的问题here但我不认识C。

我目前的解决方案涉及为单词中的每个字母创建一个字典，包含它在板上位置的元组列表，如下所示:{'letter':[(row,column),(row,column)] }.然后，对于单词中的每个字母，我检查其在棋盘上的每个位置是否与前一个字母的位置兼容。如果是，我将该位置添加到新的路径字典。

虽然对于重复字母和其他情况(如确实返回 True 的“nylon”)，这会失败。它已经相当庞大和困惑，我可能应该重新开始。我可以采用更简洁的解决方案吗？
编辑:

澄清一下:如果存在连接网格中单词中每个字母的路径，则单词“位于”网格中。允许上、下、左、右和对角线。 “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))

从那里开始，您的函数应该跟踪哪些字母已经被使用以确保它不会重复它们:

def move_valid(position, last_position):
    if last_position is None:
        return True
    return (
        abs(position[0] - last_position[0]) <= 1 and
        abs(position[1] - last_position[1]) <= 1
    )

def find_word(word, used=None):
    if word == "":
        return []
    if used is None:
        used = []
    letter, rest = word[:1], word[1:]
    for position in letter_positions.get(letter) or []:
        if position in used:
            continue
        if not move_valid(position, used and used[-1]):
            continue
        path = find_word(rest, used + [position])
        if path is not None:
            return [position] + path
    return None

例如:

>>> 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] 和 [position] + path(每个这将导致分配+复制)。在实践中，这将是 ~O(word length ^ 2)，但可以使用一些更合理的数据结构改进为 ~O(word length)。