79. 单词搜索

回溯

class Solution {

    int m;
    int n;
    boolean[][] used;

    /**
     * 使用辅助数组来进行上右下左遍历
     */
    int[][] move = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public boolean exist(char[][] board, String word) {

        m = board.length;
        n = board[0].length;
        used = new boolean[m][n];

        /**
         * 对于二维数组，要挨个进行遍历回溯
         * 只要任意一个元素开头的情况为真，就找到了
         */
        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                if (backtracking(board, word, 0, i, j)){
                    return true;
                }
            }
        }

        return false;
    }

    public boolean backtracking(char[][] board, String word, int startIndex, int row, int col){

        /**
         * 终止条件
         * 如果递归到最后一个字符，就直接判断最后一个字符和当前二维数组的元素是否相等
         */
        if (startIndex == word.length() - 1){
            return board[row][col] == word.charAt(startIndex);
        }

        /**
         * 只有当前二维数组的元素和当前字符相等时才会进行判断
         */
        if (board[row][col] == word.charAt(startIndex)){

            used[row][col] = true;

            /**
             * 使用辅助数组来进行上右下左寻找下一个字符
             */
            for (int i = 0; i < 4; i++) {

                int newRow = row + move[i][0];
                int newCol = col + move[i][1];

                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !used[newRow][newCol] && backtracking(board, word, startIndex + 1, newRow, newCol)){
                    return true;
                }
            }

            /**
             * 如果当前字符附近没有找到下一个字符，就进行回溯
             */
            used[row][col] = false;
        }

        return false;
    }
}

/**
 * 时间复杂度 O(m×n×m×n)
 * 空间复杂度 O(m×n)
 */

https://leetcode-cn.com/problems/word-search/