面试题12. 矩阵中的路径

题目

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的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

注意：本题与主站 79 题相同：https://leetcode-cn.com/problems/word-search/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法

比较简单的回溯，我用了一个表来记录走过的路径，特别注意的是回溯到上一层的时候（函数结束）要还原回去。
还有用了一个全局变量来表示是否找到。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        self.board = board
        self.word_list = [c for c in word]
        self.length = len(self.word_list)
        self.ans = False

        for i in range(len(self.board)):
            for j in range(len(self.board[0])):
                self.table = [[0]*len(self.board[0]) for _ in range(len(self.board))]
                self.find(i,j,0)
                if self.ans :
                    return True
        return False

    def find(self, i, j, str_index):
        # 判读是否已成
        if self.ans:
            return

        # 边界判断
        if i < 0 or i >= len(self.board) or j < 0 or j >= len(self.board[0]) or self.table[i][j]==1:
            return 

        if self.board[i][j] == self.word_list[str_index] :
            # 可能是对的路
            self.table[i][j] = 1
            str_index += 1
            # 完结
            if str_index == self.length:
                self.ans = True
                return
            # 继续走
            self.find(i+1,j,str_index)
            self.find(i,j+1,str_index)
            self.find(i-1,j,str_index)
            self.find(i,j-1,str_index)
        self.table[i][j] = 0

总结

代码写得比较乱，但是总体思路没有问题。
需要整理。

来自leetcode精选题解的代码：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
            if k == len(word) - 1: return True
            tmp, board[i][j] = board[i][j], '/'
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = tmp
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True
        return False

作者：jyd
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这个写得真简洁啊。
用board自身作为路径，不过访问过用'/'标记这个方法，在字符串中本身就有的话就不好使了。

所以根据以上的略改版本：

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows = len(board)
        cols= len(board[0])
        table = [[0]*cols for _ in range(rows)]
        def dfs(i,j,index):
            if not 0<=i<rows or not 0<=j<cols or board[i][j] != word[index] or table[i][j] == 1:
                return False
            # 这个容易忘记。。。
            if index == len(word)-1:return True
            table[i][j] = 1
            ans = dfs(i+1,j,index+1) or dfs(i-1,j,index+1) or dfs(i,j+1,index+1) or dfs(i,j-1,index+1)
            table[i][j] = 0
            return ans