79. Word Search

# Medium

Key idea: backtracking, 回溯法

1. check up, down, left, right, if see the right letter, because word[next] can only be adjacent.

2. in order to avoid repeated checking, set the board[index] = '0'

还需要练习

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        # edge case
        if len(board) == 0 or len(board[0]) == 0:
            return False
        
        # regular case
        for i in range(len(board)):
            for j in range(len(board[0])):
                if self.find(board, word, 0, i, j) == True:
                    return True
            
        return False
        
    def find(self, board, word, x, i, j):
        # stop condition
        if x == len(word):
            return True
        
        # regular case
        m = len(board) - 1
        n = len(board[0]) - 1
        if i < 0 or i > m or j < 0 or j > n or board[i][j] != word[x]:
            return False
    
        tmp = board[i][j]
        board[i][j] = '0'
        res = self.find(board, word, x+1, i+1, j) or self.find(board, word, x+1, i-1, j) or self.find(board, word, x+1, i, j+1) or self.find(board, word, x+1, i, j-1)
        board[i][j] = tmp
        return res

思路: Backtracking 的方法来解决这道题目。我们需要先从board中找到第一个字符出现的位置，然后从这个位置开始往上，下，左，右开始寻找；这里我们要借助一个dfs(i,j, index, board, word)的函数来寻找； 当index==word.length的时候就找到了对应的字符，返回true; 注意边界条件的check，i,j要保证在board内，或者当board[i][j]!=word.charAt(index)的时候都返回false。

复杂度： Time复杂度: 遍历整个m * n 的board的时间复杂度为m * n,对于每个点都会往上下左右来遍历寻找， k为word长度，大概要遍历4^k次，所以总的时间复杂度大概在mn4^k. Time = $O(mnk)$ Space： 由于word长度为k，recursive space大概在 $O(k)$ .