单词搜索

这个题解使用回溯法来解决单词搜索问题。从二维网格的每个位置开始，如果该位置的字符与目标单词的第一个字符匹配，就开始回溯搜索。在回溯搜索过程中，选择当前位置的上、下、左、右四个相邻位置作为下一步搜索的选择。对于每个选择，首先判断是否满足有效性条件（未越界、未访问过、字符匹配），如果满足则标记为已访问，将字符加入路径并递归搜索下一层。如果搜索到目标单词的所有字符，则返回 True。如果所有选择都搜索完毕仍未找到目标单词，则回溯到上一层，撤销当前选择的访问标记和路径。如果从所有起始位置的搜索都无法找到目标单词，则返回 False。

时间复杂度: O(m*n*4^L)

空间复杂度: O(L)

```python
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])

        def backtrack(path, visited, i, j):
            # 如果路径长度等于目标单词长度，说明找到了目标单词，返回 True
            if len(path) == len(word):
                return True
            
            # 获取当前位置的四个相邻位置作为下一步的选择
            choices = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]

            for choice in choices:
                x, y = choice
                # 判断选择是否有效：未越界、未访问过、字符匹配
                if (x, y) in visited or x < 0 or y < 0 or x >= m or y >= n or word[len(path)] != board[x][y]:
                    continue
                # 标记当前选择为已访问
                visited.add((x, y))
                # 将当前选择的字符加入路径
                path.append(board[x][y])
                # 递归搜索下一层
                if backtrack(path, visited, x, y):
                    return True
                # 回溯，撤销当前选择的路径和访问标记
                path.pop()
                visited.remove((x, y))

        # 遍历二维网格的每个位置作为起点
        for row in range(m):
            for col in range(n):
                # 如果起点字符与目标单词的第一个字符匹配，开始回溯搜索
                if board[row][col] == word[0]:
                    if backtrack([word[0]], {(row, col)}, row, col):
                        return True
        # 如果从所有起点搜索都无法找到目标单词，返回 False
        return False
```