Given an m x n board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

dfs + backtrack

注意这种回溯的题型里,最好直接修改原数据结构,如果每次都create new memory会很慢,可以用pos variable来记录位置。

Solution:

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