Word Search leetcode

Dear 丶 2022-02-16 00:37 198阅读 0赞

# Word Search #

> Given a 2D board and a word, find if the word exists in the grid.
> 
> The word can be constructed from letters of sequentially adjacent  
> cell, where "adjacent" cells are those horizontally or vertically  
> neighboring. The same letter cell may not be used more than once.
> 
> For example, Given board =
> 
>     [
>       ['A','B','C','E'],
>       ['S','F','C','S'],
>       ['A','D','E','E']
>     ]
> 
> word = "ABCCED", -> returns true, word = "SEE", -> returns true, word  
> = "ABCB", -> returns false.

## 回溯法 ##

### 说明 ###

从每一个点出发, 上下左右搜索看是否能找到相等于word的字符串. 因为每一次的访问的点不能被二次访问, 所以要维护一个m \* n 的boolean矩阵记录访问过的点.

### 复杂度 ###

因为对于每个点来说复杂度都是O(m\*n)  
所以对于总体来说 时间O(m^2n^2) 空间是boolean数组复杂度O(m\*n)

### 代码 ###

public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) {
            return true;
        }
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }
        boolean[][] visit = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
               if ( helper(board, visit, word, i, j, 0)) {
                   return true;
               }
            }
        }
        return false;
    }
    public boolean helper(char[][] board, boolean[][] visit, String word, int i, int j, int pos) {
        if (pos == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || visit[i][j] || board[i][j] != word.charAt(pos)) {
            return false;
        }
        visit[i][j] = true;
        boolean res = helper(board, visit, word, i + 1, j, pos + 1) || helper(board, visit, word, i - 1, j, pos + 1) || helper(board, visit, word, i , j - 1, pos + 1) || helper(board, visit, word, i, j + 1, pos + 1);
        visit[i][j] = false;
        return res;
    }