请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[[“a”,“b”,“c”,“e”],
[“s”,“f”,“c”,“s”],
[“a”,“d”,“e”,“e”]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 1：

输入：

• board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”

输出：

• true

示例 2：

输入：

• board = [[“a”,“b”],[“c”,“d”]], word = “abcd”
  输出：
• false

提示：
1 <= board.length <= 200
1 <= board[i].length <= 200
方法一：递归

class Solution_:def exist(self, board: List[List[str]], word: str) -> bool:"""算法思想：回溯思想，深度遍历，使用栈递归复杂度分析：M, NM,N 分别为矩阵行列大小， KK 为字符串 word 长度。时间复杂度 O((3^K)MN)：最差情况下，需要遍历矩阵中长度为 KK 字符串的所有方案，时间复杂度为 O(3^K)；矩阵中共有 MN 个起点，时间复杂度为 O(MN)O(MN) 。方案数计算： 设字符串长度为 KK ，搜索中每个字符有上、下、左、右四个方向可以选择，舍弃回头（上个字符）的方向，剩下 33 种选择，因此方案数的复杂度为 O(3^K)。空间复杂度 O(K)：搜索过程中的递归深度不超过 KK ，因此系统因函数调用累计使用的栈空间占用 O(K)O(K) （因为函数返回后，系统调用的栈空间会释放）。最坏情况下 K = MNK=MN ，递归深度为 MNMN ，此时系统栈使用 O(MN)O(MN) 的额外空间。:param board::param word::return:"""row_num = len(board)  # board行数col_num = len(board[0])  # board列数word_num = len(word)  # 字符串长度if not board and not word and row_num * col_num < word_num:  # 输入不符合条件的多种情况return Falseif word_num == 1:  # 字符串长度为1时for i in range(row_num):for j in range(col_num):if board[i][j] == word:return True# board中的每一个元素作为起始位置遍历一次for i in range(row_num):for j in range(col_num):if board[i][j] == word[0]:if self.recusion_visit(board, i, j, row_num, col_num, word, word_num, 0):  # 以当前元素为起始点进行遍历return True  # 在board中找到字符串返回Truereturn False  # 在board中没有找到字符串返回Falsedef recusion_visit(self, board, row, col, row_num, col_num, word, word_num, k):if k == word_num - 1 and board[row][col] == word[k]:  # 判断是否成功return Trueif board[row][col] == word[k]:  # 判断当前元素是否为word[k]temp = board[row][col]  # 保存board[row][col]，为了在深度遍历失败时恢复为原元素board[row][col] = '/'  # 修改board[row][col]为‘/’，表示board[row][col]已访问过# 左left_row = row  # 计算中心元素左边元素的行下标left_col = col - 1  # 计算中心元素左边元素的列下标# 下under_row = row + 1  # 计算中心元素下边元素的行下标under_col = col  # 计算中心元素下边元素的列下标# 右right_row = row  # 计算中心元素右边元素的行下标right_col = col + 1  # 计算中心元素右边元素的列下标# 上on_row = row - 1  # 计算中心元素上边元素的行下标on_col = col  # 计算中心元素上边元素的列下标if left_col >= 0:  # 深度遍历中心元素的左元素if self.recusion_visit(board, left_row, left_col,  row_num, col_num, word, word_num, k+1):return Trueif under_row < row_num:  # 深度遍历中心元素的下元素if self.recusion_visit(board, under_row, under_col, row_num, col_num, word, word_num, k+1):return Trueif right_col < col_num: # 深度遍历中心元素的右元素if self.recusion_visit(board, right_row, right_col, row_num, col_num, word, word_num, k+1):return Trueif on_row >= 0:  # 深度遍历中心元素的上元素if self.recusion_visit(board, on_row, on_col, row_num, col_num, word, word_num, k+1):return Trueboard[row][col] = tempreturn Falseif __name__ == '__main__':solution = Solution_()board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]word = "ABCCED"result = solution.exist(board, word)print(result)  # Trueboard = [["a"]]word = "a"result = solution.exist(board, word)print(result)  # Trueboard = [["a"]]word = "ab"result = solution.exist(board, word)print(result)  # Falseboard = [["a", "b"], ["c", "d"]]word = "abcd"result = solution.exist(board, word)print(result)  # Falseboard = [["C", "A", "A"], ["A", "A", "A"], ["B", "C", "D"]]word = "AAB"result = solution.exist(board, word)print(result)  # Trueboard = [["A", "B", "C", "E"], ["S", "F", "E", "S"], ["A", "D", "E", "E"]]word = "ABCESEEEFS"result = solution.exist(board, word)print(result)  # Trueboard = [["F", "Y", "C", "E", "N", "R", "D"],["K", "L", "N", "F", "I", "N", "U"],["A", "A", "A", "R", "A", "H", "R"],["N", "D", "K", "L", "P", "N", "E"],["A", "L", "A", "N", "S", "A", "P"],["O", "O", "G", "O", "T", "P", "N"],["H", "P", "O", "L", "A", "N", "O"]]word = "POLAND"result = solution.exist(board, word)print(result)  # True"""
运行结果:
True
True
False
False
True
True
TrueProcess finished with exit code 0
"""

方法二：非递归

from typing import List
from collections import dequeclass Solution:def exist(self, board: List[List[str]], word: str) -> bool:"""算法思想：回溯思想，深度遍历，使用栈代替递归面试，笔试中不建议使用，因思想易想到，但需细节考虑过多，代码量大，过于耗费时间；建议使用递归。:param board::param word::return:"""row_num = len(board)  # board行数col_num = len(board[0])  # board列数word_num = len(word)  # 字符串长度if not board and not word and row_num * col_num < word_num:  # 输入不符合条件的多种情况return Falseif word_num == 1:  # 字符串长度为1时for i in range(row_num):for j in range(col_num):if board[i][j] == word:return Truetemp_stack = deque()  # 栈，用于回溯操作，深度遍历# board中的每一个元素作为起始位置遍历一次for i in range(row_num):for j in range(col_num):if self.center_board_elem(board, i, j, row_num, col_num, word, word_num, temp_stack):  # 以当前元素为起始点进行遍历return True  # 在board中找到字符串返回Truereturn False  # 在board中没有找到字符串返回Falsedef center_board_elem(self, board, row, col, row_num, col_num, word, word_num, temp_stack):"""以board[i][j]为起始点进行遍历:param i: 在board中的行:param j: 在board中的列:param temp_stack: 栈，用于回溯操作，深度遍历:param row_num: board的行数:param col_num: board的列数:param word_num: 字符串的长度:return: 找到返回True，未找到返回False"""if board[row][col] == word[0]:  # 判断当前字符是否是word的第一个字符temp_stack.append((row, col, board[row][col], None))  # 将中心元素入栈(行，列，元素，中心元素的位置)relative_center = 'center'  # 初始时board[row][col]中心元素，设置为centerboard[row][col] = '/'  # 将中心元素设置为‘/’，表示已访问过，避免多次遍历m = row  # m为中心元素的行，初始设置为rown = col  # n为中心元素的列，初始设置为colk = 1  # k初始设置为1，表word的第二个字符，因第一个字符已匹配，一些初始化操作已完成while k < word_num:  # 遍历word中的每一个字符while temp_stack:  # 寻找word[k]，直到找到退出循环；或没找到word[k]，直到temp_stack为空时退出循环if relative_center == 'center':  # 表示board[m][n]为中心元素# 左left_row = m  # 计算中心元素左边元素的行下标left_col = n - 1  # 计算中心元素左边元素的列下标# 下under_row = m + 1  # 计算中心元素下边元素的行下标under_col = n  # 计算中心元素下边元素的列下标# 右right_row = m  # 计算中心元素右边元素的行下标right_col = n + 1  # 计算中心元素右边元素的列下标# 上on_row = m - 1  # 计算中心元素上边元素的行下标on_col = n  # 计算中心元素上边元素的列下标if left_col >= 0 and  board[left_row][left_col] == word[k]:  # 中心元素的左边元素是否是word[k]# 将中心元素更新为当前中心元素的左元素m = left_row  # 更新中心元素的行下标n = left_col  # 更新中心元素的列下标temp_stack.append((m, n, board[m][n], 'left'))  # 将新的中心元素入栈board[m][n] = '/'  # 表示新的中心元素已访问relative_center = 'center'  # 表示board[m][n]相对于新的中心元素的位置为centerif k == word_num - 1:  # 判断新的中心元素即board[m][n]是否是word的最后一个字符return True  # 找到返回Truebreakelif under_row < row_num and board[under_row][under_col] == \word[k]:  # 中心元素的下边元素是否是word[k]# 将中心元素更新为当前中心元素的下元素m = under_row  # 更新中心元素的行下标n = under_col  # 更新中心元素的列下标temp_stack.append((m, n, board[m][n], 'under'))  # 将新的中心元素入栈board[m][n] = '/'  # 表示新的中心元素已访问relative_center = 'center'  # 表示board[m][n]相对于中心元素的位置为centerif k == word_num - 1:   # 判断新的中心元素即board[m][n]是否是word的最后一个字符return True  # 找到返回Truebreak  # word[k]已找到，需退出循环"while temp_stack: ",寻找word[k+1]elif right_col < col_num and board[right_row][right_col] == \word[k]:  # 中心元素的右边元素是否是word[k]# 将中心元素更新为当前中心元素的右元素m = right_row  # 更新中心元素的行下标n = right_col  # 更新中心元素的列下标temp_stack.append((m, n, board[m][n], 'right'))  # 将新的中心元素入栈board[m][n] = '/'  # 表示新的中心元素已访问relative_center = 'center'  # 表示board[m][n]相对于中心元素的位置为centerif k == word_num - 1:   # 判断新的中心元素即board[m][n]是否是word的最后一个字符return True  # 找到返回Truebreak  # word[k]已找到，需退出循环"while temp_stack: ",寻找word[k+1]elif on_row >= 0 and board[on_row][on_col] == word[k]:  # 中心元素的上边元素是否是word[k]# 将中心元素更新为当前中心元素的上元素m = on_row  # 更新中心元素的行下标n = on_col  # 更新中心元素的列下标temp_stack.append((m, n, board[m][n], 'on'))  # 将新的中心元素入栈board[m][n] = '/'  # 表示新的中心元素已访问relative_center = 'center'  # 表示board[m][n]相对于中心元素的位置为centerif k == word_num - 1:   # 判断新的中心元素即board[m][n]是否是word的最后一个字符return True  # 找到返回Truebreak  # word[k]已找到，需退出循环"while temp_stack: ",寻找word[k+1]else:# 未找到word[k],需回退到word[k-1],即需做一些出栈恢复操作k -= 1  # 回退到word[k-1]relative_center, left_row, left_col, under_row, under_col, right_row, right_col, on_row, on_col = \self.back_restore(board, temp_stack, row_num, col_num)  # 出栈恢复操作if k == 0:breakk += 1return False  # 以board[i][j]为起始位置没找到word字符串返回Falsedef back_restore(self, board, temp_stack, row_num, col_num):"""出栈回复操作:param temp_stack: 栈，用于回溯操作，深度遍历:param row_num:  board的行数:param col_num:  board的列数:return: relative_center, left_row, left_col, under_row, under_col, right_row, right_col, on_row, on_col"""relative_center = Noneleft_row = left_col = under_row = under_col = right_row = right_col = on_row = on_col = 0if len(temp_stack) != 1:  # 栈中只有一个元素时表示以该元素为起始位置在board中未找到wordtemp = temp_stack.pop()  # 出栈，该元素作为中心元素，中心元素左下右上都未找到word中该元素的下一个元素，因此弹出relative_center = temp[3]  # 获取该元素相对于新的中心元素【即栈顶元素】的位置board[temp[0]][temp[1]] = temp[2]  # 恢复'/'为原始字符center = temp_stack.pop()  # 从栈顶获取中心元素，但并不出栈，因此还需再次将其入栈temp_stack.append(center)  # 入栈m = center[0]  # 新中心元素的行下标n = center[1]  # 新中心元素的列下标if relative_center == 'left':# 中心元素相对于新中心元素的位置未left时，获取新中心元素的左下右上元素的位置# 左left_row = left_col = -1  # 表示已遍历过，让位置溢出，避免再次访问# 下under_row = m + 1under_col = n# 右right_row = mright_col = n + 1# 上on_row = m - 1on_col = nelif relative_center == 'under':# 左left_row = left_col = -1  # 表示已遍历过，让位置溢出，避免再次访问# 下under_row = under_col = row_num  # 表示已遍历过，让位置溢出，避免再次访问# 右right_row = mright_col = n + 1# 上on_row = m - 1on_col = nelif relative_center == 'right':# 左left_row = left_col = -1  # 表示已遍历过，让位置溢出，避免再次访问# 下under_row = under_col = row_num  # 表示已遍历过，让位置溢出，避免再次访问# 右right_row = right_col = col_num  # 表示已遍历过，让位置溢出，避免再次访问# 上on_row = m - 1on_col = nelse:# 左left_row = left_col = -1  # 表示已遍历过，让位置溢出，避免再次访问# 下under_row = under_col = row_num  # 表示已遍历过，让位置溢出，避免再次访问# 右right_row = right_col = col_num  # 表示已遍历过，让位置溢出，避免再次访问# 上on_row = on_col = -1  # 表示已遍历过，让位置溢出，避免再次访问else:# 栈中只有一个元素时表示以该元素为起始位置在board中未找到wordtemp = temp_stack.pop()board[temp[0]][temp[1]] = temp[2]  # 恢复操作，‘/’恢复未原始字符return relative_center, left_row, left_col, under_row, under_col, right_row, right_col, on_row, on_colif __name__ == '__main__':solution = Solution()board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]]word = "ABCCED"result = solution.exist(board, word)print(result)  # Trueboard = [["a"]]word = "a"result = solution.exist(board, word)print(result)  # Trueboard = [["a"]]word = "ab"result = solution.exist(board, word)print(result)  # Falseboard = [["a", "b"], ["c", "d"]]word = "abcd"result = solution.exist(board, word)print(result)  # Falseboard = [["C", "A", "A"], ["A", "A", "A"], ["B", "C", "D"]]word = "AAB"result = solution.exist(board, word)print(result)  # Trueboard = [["A", "B", "C", "E"], ["S", "F", "E", "S"], ["A", "D", "E", "E"]]word = "ABCESEEEFS"result = solution.exist(board, word)print(result)  # Trueboard = [["F", "Y", "C", "E", "N", "R", "D"],["K", "L", "N", "F", "I", "N", "U"],["A", "A", "A", "R", "A", "H", "R"],["N", "D", "K", "L", "P", "N", "E"],["A", "L", "A", "N", "S", "A", "P"],["O", "O", "G", "O", "T", "P", "N"],["H", "P", "O", "L", "A", "N", "O"]]word = "POLAND"result = solution.exist(board, word)print(result)  # True"""
运行结果：
True
True
False
False
True
True
TrueProcess finished with exit code 0
"""

[题目来源于leetcode剑指offer]