79 单词搜索

一、题目

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

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

二、题解

思路：回溯 / DFS

1. 核心思路

这道题要求我们在二维网格中寻找一个单词。

因为单词可以从任意位置开始，并且每一步只能向上下左右四个方向移动，所以可以使用 DFS 从每一个格子开始搜索。

搜索过程中，需要保证：

  • 当前字符必须和 word 中对应位置的字符相同；
  • 不能越界；
  • 同一个格子不能重复使用；
  • 如果当前路径走不通，需要恢复现场，继续尝试其他路径。

所以这是一道典型的回溯题。

2. 具体步骤

  1. 遍历整个二维数组中的每一个位置，把每个位置都当作搜索起点。
  2. 从当前位置开始进行 DFS，判断当前字符是否等于 word 中对应位置的字符。
  3. 如果匹配成功，就继续向上下左右四个方向搜索下一个字符。
  4. 为了防止同一个格子被重复使用，需要临时标记当前格子已经访问过。
  5. 当前路径搜索结束后，要恢复当前格子的原字符。
  6. 如果某条路径能够完整匹配整个 word，返回 true。
  7. 如果所有起点都无法匹配，最终返回 false。

3. 关键逻辑

  • 如果 index == word.length()，说明整个单词已经匹配完成，返回 true。
  • 如果当前位置越界，说明不能继续搜索，返回 false。
  • 如果当前字符和 word.charAt(index) 不相等，说明当前路径不符合要求，返回 false。
  • 如果当前字符匹配成功，就将当前格子临时标记为 '#'，表示已经访问过。
  • 然后继续向上下左右四个方向搜索 index + 1。
  • 搜索结束后，需要恢复当前格子的原字符，这一步就是回溯。
  • 最终只要四个方向中有一个方向可以匹配成功，就返回 true。

三、代码

class Solution {
    public boolean exist(char[][] board, String word) {
        // 1. 获取二维网格的行数和列数
        int m = board.length;
        int n = board[0].length;

        // 2. 枚举每一个格子，尝试把它作为单词的起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果从当前位置开始可以找到 word，直接返回 true
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }

        // 3. 所有位置都尝试过，仍然找不到，返回 false
        return false;
    }

    /**
     * 从 board[i][j] 开始，判断能否匹配 word[index] 以及后面的字符
     *
     * @param board 二维字符网格
     * @param word  目标单词
     * @param i     当前行
     * @param j     当前列
     * @param index 当前需要匹配 word 的下标
     */
    private boolean dfs(char[][] board, String word, int i, int j, int index) {
        // 1. 如果 index 已经等于 word.length()
        // 说明 word 中的所有字符都已经匹配完成
        if (index == word.length()) {
            return true;
        }

        int m = board.length;
        int n = board[0].length;

        // 2. 边界判断：如果越界，返回 false
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return false;
        }

        // 3. 如果当前字符和 word[index] 不相等，返回 false
        if (board[i][j] != word.charAt(index)) {
            return false;
        }

        // 4. 记录当前字符，后面回溯时需要恢复
        char temp = board[i][j];

        // 5. 标记当前格子已经访问过
        // 防止同一个格子在当前路径中被重复使用
        board[i][j] = '#';

        // 6. 向上下左右四个方向继续搜索下一个字符
        boolean found = dfs(board, word, i + 1, j, index + 1)
                     || dfs(board, word, i - 1, j, index + 1)
                     || dfs(board, word, i, j + 1, index + 1)
                     || dfs(board, word, i, j - 1, index + 1);

        // 7. 回溯：恢复当前格子的原字符
        board[i][j] = temp;

        // 8. 返回四个方向的搜索结果
        return found;
    }
}

四、复杂度分析

时间复杂度：O(m×n×4L)O(m \times n \times 4^L)

说明：

其中 m 是网格的行数，n 是网格的列数，L 是字符串 word 的长度。

最坏情况下，每一个格子都可能作为搜索起点。

从每个起点出发，每一步最多可以向上下左右四个方向继续搜索，所以时间复杂度可以近似看作 O(m×n×4L)O(m \times n \times 4^L)。

空间复杂度：O(L)O(L)

说明：

递归搜索的深度最多为单词 word 的长度 L。

由于我们直接在原数组 board 上进行临时标记，没有额外使用访问数组，所以额外空间主要来自递归调用栈。

评论