79.-dan-ci-sou-suo.md

79. 单词搜索

https://leetcode-cn.com/problems/word-search/

解法一：回溯

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        for i in range(len(board)):
            for j in range(len(board[0])):
                #对棋盘每个位置，调用一次dfs算法
                if self.dfs(board, word, i, j):
                    return True              
        return False
    
    def dfs(self, board, word, i, j):   #word为待匹配串
        #待匹配串为空，说明全部匹配
        if len(word) == 0:
            return True
        #下标越界，或者该位置已访问过
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] == '.':
            return False
        #若该位置字符与待匹配串首字符匹配
        if board[i][j] == word[0]:
            board[i][j] = '.'   #标记为已访问
            #对左右上下递归，待匹配串前进一位
            res = self.dfs(board, word[1:], i, j - 1) or \
                self.dfs(board, word[1:], i, j + 1) or \
                self.dfs(board, word[1:], i - 1, j) or \
                self.dfs(board, word[1:], i + 1, j)
            board[i][j] = word[0]   #还原现场
            return res