# 单词搜索

描述

给出一个二维的字母板和一个字符串单词，寻找字母板网格中是否存在这个字符串单词。

字符串单词可以由按顺序的相邻单元的字母组成，其中相邻单元指的是水平或者垂直方向相邻。

每个单元中的字母最多只能使用一次。

字母矩阵的维度均不超过100，字符串长度不超过100。

样例

**样例 1：**

输入：

```
board = ["ABCE","SFCS","ADEE"]word = "ABCCED"
```

输出：

```
true
```

解释：

\[

A B C E

S F C S

A D E E

]

(0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,1)

**样例 2：**

输入：

```
board = ["z"]word = "z"
```

输出：

```
true
```

解释：

\[ z ]

(0,0)

分析：

用回溯backtracking, 区别dfs和backtrack和dp with memo:

回溯有剪枝，放弃无效路径立刻回溯，是特殊的dfs。普通dfs会遍历所有的可能性。而回溯通常只有一个Unique path

dp带memo是有大量重复子问题，需要保存，占内存。

本体有剪枝，重复子问题少，减枝，无需保存子状态。

注意需要记录已经visited过的点，这里直接每次递归前替换来处的点，而不是创建整个m\*n数组来记载visited.

```python
from typing import (
    List,
)
from functools import lru_cache
class Solution:
    """
    @param board: A list of lists of character
    @param word: A string
    @return: A boolean
    """
    def exist(self, board: List[List[str]], word: str) -> bool:
        # write your code here
        #dp[m][n] = dp[m-1][n] or dp[m][n-1]
        if not word:
            return True
        if not board:
            return False
        directions= {(0,1),(0,-1),(1,0),(-1,0)}
        n,m = len(board),len(board[0])
     
        def helper(x:int, y:int, i:int) -> bool:           
            if i == len(word):
                return True
            if not (0<=x< n and 0<=y<m) or word[i] != board[x][y]:
                return False

            temp = board[x][y]
            board[x][y] = '#'
            for dx,dy in directions:
                nx,ny = x+dx, y+dy
                if helper(nx,ny,i+1):
                    return True 

            board[x][y] = temp
            return False


        for i in range(n):
            for j in range(m):
                if board[i][j] == word[0] and helper(i,j,0):
                    return True
        return False

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/meta-2024/dan-ci-sou-suo.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.