LeetCode 79. 单词搜索

Categories:

Tags:

题目描述
思路分析
1. 解法一：回溯 DFS（推荐）
相似题目

题目描述

✅ 79. 单词搜索

思路分析

解法一：回溯 DFS（推荐）

核心思路：

从矩阵中任意一个与 word[0] 匹配的格子出发，沿上下左右四个方向递归尝试匹配后续字符。

用”原地标记”防止重复访问：将当前格子暂时改为 '#'，DFS 返回后恢复原值（回溯），无需额外 visited 数组。

终止条件：当匹配索引 k == len(word) - 1 时说明完整匹配，返回 true；越界或字符不符时剪枝，返回 false。

优化剪枝：出发前统计矩阵字符频率，若 word 首字符出现次数多于尾字符，则翻转 word 从尾部开始搜索，可大幅减少分支数。

复杂度分析：

时间复杂度：O(m × n × 4^L)，其中 m、n 为矩阵行列数，L 为单词长度，每个格子最多向 4 方向扩展 L 层

空间复杂度：O(L)，递归调用栈深度等于单词长度

{% raw %}

class Solution {
    private static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private char[][] board;
    private String word;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        int m = board.length, n = board[0].length;
        // 枚举所有起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(int i, int j, int k) {
        // 当前字符不匹配，剪枝
        if (board[i][j] != word.charAt(k)) {
            return false;
        }
        // 已匹配最后一个字符，成功
        if (k == word.length() - 1) {
            return true;
        }
        // 原地标记已访问，防止重复使用
        char tmp = board[i][j];
        board[i][j] = '#';
        int m = board.length, n = board[0].length;
        for (int[] d : DIRS) {
            int ni = i + d[0], nj = j + d[1];
            if (ni >= 0 && ni < m && nj >= 0 && nj < n) {
                if (dfs(ni, nj, k + 1)) {
                    // 回溯恢复后返回
                    board[i][j] = tmp;
                    return true;
                }
            }
        }
        // 回溯：恢复原字符
        board[i][j] = tmp;
        return false;
    }
}

{% endraw %}

{% raw %}

func exist(board [][]byte, word string) bool {
    m, n := len(board), len(board[0])
    dirs := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

    var dfs func(i, j, k int) bool
    dfs = func(i, j, k int) bool {
        // 当前字符不匹配，剪枝
        if board[i][j] != word[k] {
            return false
        }
        // 已匹配最后一个字符，成功
        if k == len(word)-1 {
            return true
        }
        // 原地标记已访问
        tmp := board[i][j]
        board[i][j] = '#'
        for _, d := range dirs {
            ni, nj := i+d[0], j+d[1]
            if ni >= 0 && ni < m && nj >= 0 && nj < n {
                if dfs(ni, nj, k+1) {
                    // 回溯恢复后返回
                    board[i][j] = tmp
                    return true
                }
            }
        }
        // 回溯：恢复原字符
        board[i][j] = tmp
        return false
    }

    // 枚举所有起点
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if dfs(i, j, 0) {
                return true
            }
        }
    }
    return false
}

{% endraw %}

相似题目

题目	难度	考察点
212. 单词搜索 II	困难	字典树 + 回溯 DFS
980. 不同路径 III	困难	回溯、矩阵路径
200. 岛屿数量	中等	DFS / BFS 矩阵
695. 岛屿的最大面积	中等	DFS 矩阵
329. 矩阵中的最长递增路径	困难	DFS + 记忆化搜索
130. 被围绕的区域	中等	DFS / BFS 矩阵
417. 太平洋大西洋水流问题	中等	多源 DFS 矩阵

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/69215547