剑指offer-12

题目

结果

代码

class Solution {
    private static final char VISITED = '/';

    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (search(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean search(char[][] board, String word, int row, int col, int index) {
        // 是否越界或访问过或不符合预期
        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] == VISITED || board[row][col] != word.charAt(index)) {
            return false;
        }
        // 已经找到合适的序列
        if (index == word.length() - 1) {
            return true;
        }
        // 标记避免重复访问
        char tmp = board[row][col];
        board[row][col] = VISITED;
        // 上下左右递归
        if (search(board, word, row - 1, col, index + 1) || search(board, word, row + 1, col, index + 1) || search(board, word, row, col + 1, index + 1) || search(board, word, row, col - 1, index + 1)) {
            return true;
        } else {
            // 恢复
            board[row][col] = tmp;
            return false;
        }
    }
}

复杂度

时间复杂度：大于O（m×n）

空间复杂度：O（index），最大递归深度不超过index