Leetcode79. 单词搜索

题目传送地址： https://leetcode.cn/problems/word-search/submissions/

运行效率：

代码如下：

//回溯法，递归 
 public static boolean exist(char[][] board, String word) {
    
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < board.length; i++) {
    
            for (int j = 0; j < board[0].length; j++) {
    
                if (board[i][j] == word.charAt(0)) {
    
                    if (recur(i, j, board, word, 0, set)) {
    
                        return true;
                    }
                }
            }
        }
        return false;
    }

//注意要在recur函数的开头set.add(row + ":" + col); 且在结尾要 set.remove(row + ":" + col); 这才是回溯的状态的还原
    public static boolean recur(int row, int col, char[][] board, String word, int k, HashSet<String> set) {
    
        //处理边界情况
        if (k == word.length() - 1) {
    
            if (board[row][col] == word.charAt(k)) {
    
                set.add(row + ":" + col);
                return true;
            }
            return false;
        }
        if (board[row][col] != word.charAt(k)) {
    
            return false;
        }
        //当前坐标的元素能不能成为贪吃蛇的蛇头， 取决于左、右、下 三个位置的情况
        boolean bottom;
        boolean left;
        boolean right;
        boolean top;
        set.add(row + ":" + col);
        boolean result = false;
        //下边相邻的坐标
        if (row + 1 < board.length && !set.contains((row + 1) + ":" + col)) {
    
            bottom = recur(row + 1, col, board, word, k + 1, set);
            if (bottom) {
    
                result = true;
            }
        }
        //左边相邻的坐标
        if (col - 1 >= 0 && !set.contains(row + ":" + (col - 1))) {
    
            left = recur(row, col - 1, board, word, k + 1, set);
            if (left) {
    
                result = true;
            }
        }
        //右边相邻的坐标
        if (col + 1 < board[0].length && !set.contains(row + ":" + (col + 1))) {
    
            right = recur(row, col + 1, board, word, k + 1, set);
            if (right) {
    
                result = true;
            }
        }
        //上边相邻的坐标
        if (row - 1 >= 0 && !set.contains((row - 1) + ":" + col)) {
    
            top = recur(row - 1, col, board, word, k + 1, set);
            if (top) {
    
                result = true;
            }
        }
        set.remove(row + ":" + col);
        return result;
    }