时间戳

首页 > 解决方案 > 回溯以找到所有可能的路径

python - 回溯以找到所有可能的路径

问题描述

在最近的一次采访中，我得到了这个问题，

给定一串字母和一个单词，找出构成单词的所有可能路径

方向：水平、垂直或对角线到距离为 1 的任意坐标

约束：每条路径必须是一组唯一的坐标。

例子：

明星 艺人
XKCS 陷阱

START - > 2

这是我的解决方案，

class WordFinder:
    def __init__(self):
        self.neighbors = [[-1, 1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]]

    def find_all_paths(self, grid, word):
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == word[0]:
                    visited = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
                    result = []
                    self.helper(grid, 0, 0, visited, word, 0, result)
                    count += len(result)
        return count

    def helper(self, grid, row, col, visited, word, index, result):
        if index == len(word):
            result.append(1)
        adjacent = []
        for item in self.neighbors:
            adjacent.append([row + item[0], col + item[1]])
        for adj in adjacent:
            if 0 <= adj[0] < len(grid) and 0 <= adj[1] < len(grid[0]):
                if not visited[adj[0]][adj[1]]:
                    if index + 1 < len(word) and grid[adj[0]][adj[1]] == word[index + 1]:
                        visited[adj[0]][adj[1]] = True
                        self.helper(grid, adj[0], adj[1], visited, word, index + 1, result)
                        visited[adj[0]][adj[1]] = False


if __name__ == '__main__':
    word_finder = WordFinder()
    print(word_finder.find_all_paths(
        [['s', 't', 'a', 'r'], ['a', 'r', 't', 'y'], ['x', 'k', 'c', 's'], ['t', 'r', 'a', 'p']],
        "start"))

这会产生错误的答案。有人可以帮助理解我的逻辑问题。

标签： pythonalgorithmdata-structuresbacktrackingrecursive-backtracking

解决方案

答案应该是 4，而不是 2，对吗？我对“所有可能的路径”和“唯一的坐标集”的解释是，相同的坐标不能在单个路径中重复使用，但不同的路径可以使用来自其他路径的坐标。

    Paths (row, col):
path1:    0 0   0 1   1 0   1 1    1 2
path2:    0 0   0 1   0 2   1 1    1 2
path3:    0 0   0 1   1 0   0 3    1 2    
path4:    2 3   1 2   0 2   1 1    0 1

我看到 3 个错误，可能还有更多：

  1. @user3386109 指出

    self.neighbors = [[-1, 1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1 ], [1, 1]]

应该

   self.neighbors = [[-1, -1], [0, -1], [1, -1], [-1, 0], [1, 0], [-1, 1], [0, 1], [1, 1]]

  1. 您每次都从 0,0 开始：

    self.helper(grid, 0, 0,visited, word, 0, result)

应该：

self.helper(grid, i, j, visited, word, 0, result)

  1. 您的终止已关闭 1：

    如果索引 == len(word):

应该

if index == len(word) - 1:

推荐阅读