python - 查找单词的位置作为字母网格中的坐标列表

Question

给定一个字母网格和一个单词列表，找到每个单词的位置作为坐标列表。结果列表可以按任何顺序排列，但必须按顺序给出单个单词的坐标。字母不能跨单词和字​​母重复使用。每个给定的单词都保证在网格中。单词的连续字母要么向下要么向右(即没有颠倒的单词或颠倒的单词部分，只有向下或向右)。
例如，给定以下网格和单词集，

 [
    ['d', 'r', 'd', 'o', 'r', 's'],
    ['o', 'b', 'i', 'g', 'n', 'c'],
    ['g', 'f', 'n', 'm', 't', 'a'],
    ['x', 's', 'i', 'a', 'n', 't']
]

words1 = [ "dog", "dogma", "cat" ]

输出坐标列表如下:

findWords(grid, words)->
  [ [ (1, 5), (2, 5), (3, 5) ], # cat
    [ (0, 2), (0, 3), (1, 3), (2, 3), (3, 3)], # dogma
    [ (0, 0), (1, 0), (2, 0) ], # dog
  ]

在这个例子中，“dogma”中的“dog”不能用于单词“dog”，因为字母不能重复使用。

Answer 1

这是我对解决方案的尝试。首先，我找到所有可能的路径来拼写任何单词。路径由它们拼写的单词索引。然后我通过一次为每个单词添加一个可能的路径，同时保持一个可见的集合来遍历所有可能的路径组合。一旦我在找到所有单词之前用完一个单词的可行路径，然后我就会回溯。

def findWords(grid, words):
    # Regular old dfs through the grid, we only go right or down
    def dfs(row, col, path, idx):
        if idx == len(word):
            if word in all_paths:
                all_paths[word].append(list(path))
            else:
                all_paths[word] = [list(path)]
        else:
            if row + 1 < len(grid):
                if grid[row+1][col] == word[idx]:
                    path.append((row+1, col))
                    dfs(row+1, col, path, idx+1)
                    path.pop()
            if col + 1 < len(grid[0]):
                if grid[row][col+1] == word[idx]:
                    path.append((row, col+1))
                    dfs(row, col+1, path, idx+1)
                    path.pop()

    # For each word, find all possible paths through the grid to spell the word
    # Each path is a collection of coordinates as is desired from the function
    # Paths are indexed by word and stored in a list in a dictionary
    all_paths = {}
    for row in range(len(grid)):
        for col in range(len(grid[0])):
            for word in words:
                if grid[row][col] == word[0]:
                    dfs(row, col, [(row, col)], 1)

    # Try all possible combinations of paths from each letter
    def dfs2(idx):
        if idx == len(words):
            return True

        word = words[idx]
        for path in all_paths[word]:
            for loc in path:
                if loc in seen:
                    return False
            for loc in path:
                seen.add(loc)
            if dfs2(idx+1):
                retlst.append(path)
                return True
            else:
                for loc in path:
                    seen.remove(loc)
        return False

    # Backtrack through possible combinations
    seen = set([])
    retlst = []
    dfs2(0)
    return retlst

可能有一种方法可以通过可能的路径组合来进行 DFS，而您正在通过需要拼写的单词进行 DFS，以避免预先计算所有路径，但这对我来说太复杂了，无法弄清楚。