回溯寻找所有可能的路径
Backtracking to find all possbile paths
我在最近的一次采访中得到了这个问题,
给定一串字母和一个单词,找到所有可能的路径
造句
方向:水平、垂直或对角线到任何距离为 1 的坐标
约束:每条路径必须是一组唯一的坐标。
示例:
S T A R
A R T Y
X K C S
T R A P
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"))
这会产生错误的答案。有人可以帮助理解我的逻辑问题吗?
答案应该是 4,而不是 2,对吗?我对"all possible paths"和"unique set of coordinates"的解释是同一个坐标不能在单一路径中重复使用,但不同的路径可能会使用其他路径的坐标。
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 个错误,可能还有更多:
@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]]
你每次都从0,0开始:
self.helper(grid, 0, 0, visited, word, 0, result)
应该是:
self.helper(grid, i, j, visited, word, 0, result)
您的终止时间为 1:
if index == len(word):
应该是
if index == len(word) - 1:
我在最近的一次采访中得到了这个问题,
给定一串字母和一个单词,找到所有可能的路径 造句
方向:水平、垂直或对角线到任何距离为 1 的坐标
约束:每条路径必须是一组唯一的坐标。
示例:
S T A R
A R T Y
X K C S
T R A P
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"))
这会产生错误的答案。有人可以帮助理解我的逻辑问题吗?
答案应该是 4,而不是 2,对吗?我对"all possible paths"和"unique set of coordinates"的解释是同一个坐标不能在单一路径中重复使用,但不同的路径可能会使用其他路径的坐标。
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 个错误,可能还有更多:
@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]]
你每次都从0,0开始:
self.helper(grid, 0, 0, visited, word, 0, result)
应该是:
self.helper(grid, i, j, visited, word, 0, result)
您的终止时间为 1:
if index == len(word):
应该是
if index == len(word) - 1: