> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/4.depth-first-search/79.-word-search-m.md).

# 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;
    }
    
}
```