📃 题目描述

题目链接：79. 单词搜索 (opens new window)

🔔 解题思路

动态图可以看这里：https://leetcode.cn/problems/word-search/solution/zai-er-wei-ping-mian-shang-shi-yong-hui-su-fa-pyth/

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return false;
        }

        for (int i = 0; i < board.length; i ++) {
            for (int j = 0; j< board[0].length; j ++) {
                boolean[][] visited = new boolean[board.length][board[0].length];
                int start = 0;
                if (dfs(board, i, j, word, start, visited)) {
                    return true;
                }
            }
        }

        return false;
    }

    // 从 board[row][col] 出发，能否匹配到 word[start, end]
    private boolean dfs(char[][] board, int row, int col, String word, int start, boolean[][] visited) {
        if (board[row][col] != word.charAt(start)) {
            return false;
        }
        // 已经匹配到 word 的最后一个元素并且 board[row][col] == word.charAt(start)
        else if (start == word.length() - 1) {
            return true;
        }
        
        // 1. 访问 board[row][col]
        visited[row][col] = true;

        // 2. 做选择: 访问 board[row][col] 的邻居节点
        int[][] neighboors = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 
        for (int[] neighboor : neighboors) {
            int i = row + neighboor[0];
            int j = col + neighboor[1];   
            if (i >= 0 && i < board.length && j >= 0 && j < board[0].length && !visited[i][j]) {
                if (dfs(board, i, j, word, start + 1, visited)) {
                    return true;
                }
            }
        }

        // 3. 回溯：以 board[row][col] 为起点，无法匹配到 word[start, end]，则进行回溯
        visited[row][col] = false;

        return false;
    }
}

为什么需要回溯？这里画个图来给大家解释下，目标字符串是 ABCESEEEFS：

假设当前遍历到 S 的位置，也就是 dfs(board, i = 1, j = 3, start = 4)

board[1, 3] 有三个邻居，上（已被访问过）下左，所以此时我们有两个选择：

• 往左走，把 visitited[1][2] 置为 true，dfs(board, i = 1, j = 2, start = 5)，也就是从 board[1][2] 开始匹配 EEEFS
• 往下走，把 visitited[2][3] 置为 true，dfs(board, 2, 3, start = 5)，也就是从 board[2][3] 开始匹配 EEEFS

假设我们先执行往左走，最终执行下来会发现往左走是行不通的，返回 false。那如果不进行回溯，visitited[1][2] 还是 true 的话，当我们执行 “往下走” 这个选择的时候，就没办法走到 board[1][2] 这个位置了

💥 复杂度分析

• 空间复杂度：，3^N 就是回溯的时间复杂度，因为每个点都有 3 个邻居，也就是每个点都可以做出三种选择，总共 N 个点，所以时间复杂度为 3^N
• 时间复杂度：O(N^2)