# Word Search

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
class Solution(object):
def exist(self, board, word):
“””
:type board: List[List[str]]
:type word: str
:rtype: bool
“””
# find the first element
# dfs
# mark current visited
# dfs next layer with word[1:]
self.ans = False
rowNum = len(board)
colNum = len(board[0])
visited = [[0 for _ in range(colNum)] for _ in range(rowNum)]
direction = [(0, 1), (1,0), (-1, 0), (0, -1)]
word = list(word)
def dfs(i, j, newWord, pos):
if visited[i][j] == 1 or self.ans:
return
visited[i][j] = 1
if pos == len(newWord)-1:
self.ans = True
return

for each in direction:
x, y = i+each[0], j+each[1]
if x < 0 or x >= rowNum or y < 0 or y >= colNum or board[x][y] != newWord[pos+1]:
continue
dfs(x, y, newWord, pos+1)
visited[i][j] = 0

for i in range(rowNum):
for j in range(colNum):
if board[i][j] == word[0]:
dfs(i,j, word, 0)
if self.ans == True:
return self.ans
return self.ans

--

--