-
Notifications
You must be signed in to change notification settings - Fork 0
/
17_Word_Search
28 lines (25 loc) · 916 Bytes
/
17_Word_Search
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
def find(grid,i,j,word,k,v):
a=b=c=d=False
if (i,j) in v:
return False
if k==len(word):
return True
if j-1>=0 and grid[i][j-1]==word[k]:
a=find(grid,i,j-1,word,k+1,v+[(i,j)])
if i-1>=0 and grid[i-1][j]==word[k]:
b=find(grid,i-1,j,word,k+1,v+[(i,j)])
if j+1<len(grid[0]) and grid[i][j+1]==word[k]:
c=find(grid,i,j+1,word,k+1,v+[(i,j)])
if i+1<len(grid) and grid[i+1][j]==word[k]:
d=find(grid,i+1,j,word,k+1,v+[(i,j)])
return a or b or c or d
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
for i in range(len(board)):
for j in range(len(board[0])):
visited=[]
if board[i][j]==word[0]:
x=find(board,i,j,word,1,visited)
if x==True:
return True
return False