# 79. Word Search

{% hint style="info" %}
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'`

还需要练习
{% endhint %}

```python
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`次，所以总的时间复杂度大概在`m`*`n`*`4^k`. Time = $$O(mnk)$$ \
Space： 由于word长度为k，recursive space大概在 $$O(k)$$ .