[数据结构与算法]LeetCode 79.单词搜索

题目：

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用

思路：

• 该题目是一道典型的深度优先搜索DFS+回溯算法题
• 首先我们可以设置一个visited[][]数组用来存储当前字符是否遍历过，防止重复遍历。设置一个curindex用来表示当前遍历到了哪一个字符串。
• 经过每一个位置的字符，都有上下左右四个位置可以走，在走之前不要忘记先对索引是否越界进行判断，如果没有越界，那么就可以走该位置
• 走过一个位置之后记得要进行回溯，也就是恢复走之前的状态，即设置visited[][]的值
• 这种题目基本都是同一个模板，换汤不换药，做多了慢慢手感就上来了

以下为代码+注释：

// 标记数组位置是否走过
    private boolean[][] visited;
    // 一共有四个可以走的方向
    private int[] dx = {1, -1, 0, 0};
    private int[] dy = {0, 0, 1, -1};
    public boolean exist(char[][] board, String word) {
        // 经典深搜DFS
        int m = board.length;
        int n = board[0].length;
        visited = new boolean[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(dfs(i, j, board, 0, word))
                    return true;
            }
        }
        return false;
    }

    public boolean dfs(int x, int y, char[][] arr, int curindex, String target){
        // 临界条件，如果当前位置是目标字符串的最后一个，就直接返回两字符是否相等
        if(curindex == target.length() - 1){
            return target.charAt(curindex) == arr[x][y];
        }
        // 设置一个布尔类型的变量表示结果
        boolean res = false;
        // 如果当前两个值相等，才有向下继续寻找的可能
        if(target.charAt(curindex) == arr[x][y]){
            // 先将该位置设置为true，表示遍历过了
            visited[x][y] = true;
            // 从该方向延伸出来上下左右四个方向继续遍历
            for(int i = 0; i < 4; i++){
                int curx = x + dx[i];
                int cury = y + dy[i];
                // 首先判断索引是否越界，目标位置是否遍历过
                if(curx >= 0 && curx < arr.length && cury >= 0 && cury < arr[0].length &&
                !visited[curx][cury]){
                    //  如果都满足，就将该字符加入，并在该基础上进行下一个位置的判断
                    res = dfs(curx, cury, arr, curindex + 1, target);
                    // 如果结果为true，就说明成功找到
                    if(res)
                        return true;
                }
            }
            // 回溯，将该位置重置为没有遍历过
            visited[x][y] = false;
        }
        return res;
    }

笔者也在不断学习，如有错误，欢迎指正！