CodingInterviews/StringPathInMatrix/StringPathInMatrix.py at master · bryceustc/CodingInterviews · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
# -*- coding:utf-8 -*-
classSolution:
defhasPath(self, matrix, rows, cols, path):
# write code here
ifmatrix==Noneorrows<1orcols<1orpath==None:
returnFalse
visited= [[0forxinrange(cols)] foryinrange(rows)]
foriinrange(0,rows):
forjinrange(0,cols):
if (self.dfs(matrix, rows, cols, i, j, path, 0, visited)):
returnTrue
returnFalse
defdfs(self, matrix, rows, cols, i, j, path, k, visited):
index=i*cols+j
ifi<0ori>=rowsorj<0orj>=colsormatrix[index]!=path[k] orvisited[i][j]==1:
returnFalse
ifk==len(path)-1:
returnTrue
visited[i][j]=1
ifself.dfs(matrix, rows, cols, i-1, j, path, k+1, visited):
returnTrue
ifself.dfs(matrix, rows, cols, i+1, j, path, k+1, visited):
returnTrue
ifself.dfs(matrix, rows, cols, i, j-1, path, k+1, visited):
returnTrue
ifself.dfs(matrix, rows, cols, i, j+1, path, k+1, visited):
returnTrue
visited[i][j]=0
returnFalse
## Solution 2:
classSolution:
defexist(self, board: List[List[str]], word: str) ->bool:
ifboard==None:
returnFalse
rows=len(board)
cols=len(board[0])
visited= [[0forxinrange(cols)] foryinrange(rows)]
foriinrange(rows):
forjinrange(cols):
ifself.dfs(board, rows, cols, i, j, word, 0, visited):
returnTrue
returnFalse
defdfs(self, board, rows, cols, i, j, word, k, visited):
ifi<0ori>=rowsorj<0orj>=colsorboard[i][j]!=word[k] orvisited[i][j]==1:
returnFalse
ifk==len(word)-1:
returnTrue
visited[i][j]=1
ifself.dfs(board, rows, cols, i-1, j, word, k+1, visited):
returnTrue
ifself.dfs(board, rows, cols, i+1, j, word, k+1, visited):
returnTrue
ifself.dfs(board, rows, cols, i, j-1, word, k+1, visited):
returnTrue
ifself.dfs(board, rows, cols, i, j+1, word, k+1, visited):
returnTrue
visited[i][j]=0
returnFalse