# 79. Word Search (M)

Given an `m x n` grid of characters `board` and a string `word`, return `true` *if* `word` *exists in the grid*.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/11/04/word2.jpg)

```
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg)

```
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
```

**Example 3:**

![](https://assets.leetcode.com/uploads/2020/10/15/word3.jpg)

```
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
```

**Constraints:**

* `m == board.length`
* `n = board[i].length`
* `1 <= m, n <= 6`
* `1 <= word.length <= 15`
* `board` and `word` consists of only lowercase and uppercase English letters.

&#x20;

**Follow up:** Could you use search pruning to make your solution faster with a larger `board`?

### Solution:

深度优先搜索

遍历board每个点，看它是否和word开头字母相同，如果相同就就进入dfs过程

dfs(board, word,now, x, y)

board是字母板，word是单词，now是已经匹配了word的位置，x，y是最后一次匹配成功的字母板的位置下标

在dfs过程中 上下左右四个方向去找能匹配word里下个字符的位置

### 时间复杂度

$O(nm\*3^length) $

O(nm)O(nm)是由于我们要遍历board每个点，判断它是否和word相同

O(3length)O(3length)是由于我们dfs过程，四个方向都要去试，但有一个方向是从上一个位置过来的方向，过来的方向是不用去搜索的了

例如

abcd，先到达(0,0)位置的a，又走到(0,1)位置的b，不用回头再走a

但因为有剪枝，所以实际状态量要比这个小不少

```
class Solution {
    
    public boolean exist(char[][] board, String word) {
        
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        int m = board.length;
        int n = board[0].length;
        boolean[][] visited  = new boolean[m][n];   
        
        for(int i = 0; i< m; i++)
        {
            for(int j = 0; j< n; j++)
            {
                if(board[i][j] == word.charAt(0))
                {
                     visited[i][j] = true;
                     if(backtracking(word, 0, board, i, j, visited))
                     {
                         return true;
                     }
                     visited[i][j] = false;
                }
            }
        }
        return false;
    }
    
    
    
    public boolean backtracking(String word, int currentIndex, char[][] board, int x, int y, boolean[][] visited)
    {
        if(word.charAt(currentIndex) != (board[x][y]))
        {
            return false;
        }
        
        if(currentIndex == word.length()-1)
        {
            return true;
        }
        
        int[] directX = {-1, 1, 0, 0};
        int[] directY = {0, 0, -1, 1};
        
        for(int i = 0; i<4; i++)
        {
            int nextX = x + directX[i];
            int nextY = y + directY[i];
            if(isBound(board, nextX, nextY) && !visited[nextX][nextY])
            {
                visited[nextX][nextY] = true;
                if(backtracking(word, currentIndex+1, board, nextX, nextY, visited))
                {
                    return true;
                }
                visited[nextX][nextY] = false;
            }
        }
        return false;
    }
    
    public boolean isBound(char[][] board, int x, int y)
    {
        int m = board.length;
        int n = board[0].length;
        if(x<0 || x>=m|| y<0 || y>=n)
        {
            return false;
        }
        return true;
    }
    
}
```


---

# 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://junnie.gitbook.io/nine-chapter/4.depth-first-search/79.-word-search-m.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.