# LeetCode: 79. 单词搜索¶

## 1、题目描述¶

board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]



## 2、解题思路¶

​ 使用深度优先搜索，对每一个开头字母能够匹配的字母，开始深度优先搜索

[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]

给定 word = "ABCCED"


​ 如果找到，返回True

​ 对每一个能匹配到的第一个字符，都这样搜索，

​ 如果全部都找不到，返回False

class Solution:
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
row = len(board)
col = len(board[0])
for i in range(row):
for j in range(col):
if word[0] == board[i][j]:
temp_visited = [[0] * col for _ in range(row)]
if self.findWord(board, word, 0, temp_visited, i, j, row, col):
return True
return False

def findWord(self, board, word, index, visited, x, y, row, col):
if index >= len(word):
return True
if x < 0 or y < 0 or x >= row or y >= col:
return False
result = False

# temp_visited = [[visited[i][j] for j in range(col)] for i in range(row)]
if visited[x][y] == 0 and board[x][y] == word[index]:
visited[x][y] = 1
result = result or self.findWord(board, word, index + 1, visited, x - 1, y, row, col)
result = result or self.findWord(board, word, index + 1, visited, x, y - 1, row, col)
result = result or self.findWord(board, word, index + 1, visited, x + 1, y, row, col)
result = result or self.findWord(board, word, index + 1, visited, x, y + 1, row, col)
else:
return False
visited[x][y] = 0
return result

• 回溯法
class Solution:
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""

if not word:
return True

row, col = len(board), len(board[0])

# 上下左右-坐标
surround = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# 坐标验证
def available(m, n):
return 0 <= m < row and 0 <= n < col

def backtrace(x, y, index):
if index == len(word) - 1:
return True

board[x][y] = "#"
for dx, dy in surround:
x1, y1 = x + dx, y + dy
if available(x1, y1) and board[x1][y1] == word[index + 1] and backtrace(x1, y1, index + 1):
return True

board[x][y] = word[index]
return False

for i in range(row):
for j in range(col):
if board[i][j] == word[0] and backtrace(i, j, 0):
return True
return False