原题
给出一个二维的字母板和一个单词，寻找字母板网格中是否存在这个单词。
单词可以由按顺序的相邻单元的字母组成，其中相邻单元指的是水平或者垂直方向相邻。每个单元中的字母最多只能使用一次。
样例
给出board =
[
"ABCE",
"SFCS",
"ADEE"
]
word = "ABCCED"， ->返回 true,
word = "SEE"，-> 返回 true,
word = "ABCB"， -> 返回 false.
解题思路
- 遍历二维数组的每一个点，当作起始点做DFS
- 在进入DFS后，对于访问过的节点标记为None，以表明访问过
- 关于回溯要注意的是，如果返回True其实就结束了，以为已经找到答案了，也不需要回溯。如果不返回True，而是改变一个全局变量self.res的值为True，会超时
完整代码
class Solution(object):
def __init__(self):
self.word = ""
def exist(self, board, word):
"""
:type board: List[List[str]]
:type word: str
:rtype: bool
"""
self.word = word
for row_num in range(len(board)):
for col_num in range(len(board[0])):
if self.search(board, row_num, col_num, 0):
return True
return False
def search(self, board, x, y, pos):
if self.word[pos] == board[x][y]:
if pos == len(self.word) - 1:
return True
else:
temp = board[x][y]
board[x][y] = None
if x + 1 < len(board) and self.search(board, x + 1, y, pos + 1):
return True
if x - 1 >= 0 and self.search(board, x - 1, y, pos + 1):
return True
if y + 1 < len(board[0]) and self.search(board, x, y + 1, pos + 1):
return True
if y - 1 >= 0 and self.search(board, x, y - 1, pos + 1):
return True
board[x][y] = temp
return False
else:
return False
