Python:在字符矩阵中找到一个单词
我正在尝试创建一个单词游戏，其中包括在一个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‘。我发现了一个类似的问题，这里，但我不知道C。
我的当前解决方案包括为单词中的每个字母创建一个字典，其中包含一个元组列表，其位置如下：{“字母”：(行，列)，(行，列)}。然后，对于单词中的每个字母，我检查其在板上的每个位置是否与上一封信的位置兼容。如果是的话，我将该位置添加到一个新的路径字典中。
这是失败的，不过，重复字母和其他情况，如“尼龙”，它确实返回了真。它已经相当笨重和混乱，我可能应该重新开始。有什么更简洁的解决方案吗？
编辑：
澄清:如果网格中存在连接单词中的每个字母的路径，则一个单词是“在”网格中。上、下、左、右和对角线是允许的。'x‘与'y’相邻，‘y’与'l‘相邻，依此类推。该路径不需要有特定的形状，只要每个字母是相邻的，没有特定的字母在板上使用两次。一个单词可以有重复的字母，所以允许使用"pama“，因为有多个a可以使用。
@MSW是正确的，游戏是扭动，虽然我是第一次发现这个！
回答 1
Stack Overflow用户
发布于 2015-07-28 21:29:53
如果您想检查word成员资格，那么将字母映射到位置的字典起点是一个很好的起点：
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 (每个used + [position]和[position] + path都将导致分配+副本)。在实践中，这将是~O(word length ^ 2)，但可以通过一些更合理的数据结构改进为~O(word length)。
https://stackoverflow.com/questions/31686957
复制相似问题
腾讯云开发者
