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:

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

Example 2:

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

Example 3:

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.

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