搜索二维数组中的序列(每个条目仅访问一次)
搜索二维数组中的序列(每个条目仅访问一次)
提问于 2016-09-20 09:03:02
这是“编程面试的元素”(17.5)一书中的一个问题。问题是：
当A是一个矩阵，S是一个整数数组时，如果你能从A中的某一项开始，按S规定的顺序遍历A中的相邻项，我们就说S出现在A中。相邻项是顶部、底部、左侧和右侧的项。
例如，如果A=
[1 2 3
3 4 5
5 6 7]
S=1 3 4 6
则S在A中，因为A= 1，A1 = 3，A1 = 4，A2 =6
但如果S=1 2 3 4，则S不在A中。
如果可以多次访问A中的条目，我知道如何使用递归解决问题。
但是，如果有一个额外的约束，即每个条目最多只能访问一次，我如何有效地解决这个问题呢？
回答 1
Stack Overflow用户
发布于 2019-06-12 03:06:44
如果访问被解释为“不按给定的顺序访问单元格”，也就是说，在算法过程中可以多次访问单元格，那么我能想到的最好的解决方案具有指数时间复杂度。
跟踪沿给定路径访问的单元格的要点：
from typing import Set, Tuple
def is_pattern_contained_in_grid(grid, S):
def traverse(x, y, s_idx, visited: Set[Tuple[int,int]]):
if (s_idx == len(S)):
return True
if ((x, y) in visited
or not( x >= 0 and y >= 0 and x < n and y < m)
or grid[x][y] != S[s_idx]):
return False
for adj_x, adj_y in ((x + 1, y),
(x - 1, y),
(x, y + 1),
(x, y - 1)):
if (traverse(adj_x, adj_y, s_idx + 1, visited.union({(x,y)}))):
return True
return False
if (not S):
return True
n = len(grid)
m = len(grid[0])
for i in range(n*m):
x = i % n
y = i // n
if (traverse(x, y, 0, set())):
return True
return False
# Some examples
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,1],[0,3,4,0],[1,5,6,7]], [1,5,3,1,3,1]))
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,7],[0,3,4,0],[1,5,6,7]], [1,5,3,1,3,1]))
print(is_pattern_contained_in_grid([[0,0,0,0],[0,1,3,1],[0,3,4,0],[1,5,6,7]], [1,5,3,5,6]))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/39584214
复制相关文章
相似问题