LeetCode 79. 单词搜索

2026-06-03 HGNULB 约 8 分钟

文章信息 22 个分类 5 个标签

分类

LeetCode CodeTop 中等已解决 50-100 LeetCode 热题 100 面试经典 150 题腾讯字节阿里华为微软亚马逊美团拼多多小米快手携程 B站虾皮商汤猿辅导

题目描述

✅ 79. 单词搜索

题意分析

在字符网格中寻找一条路径，使路径上的字符按顺序拼成给定单词。每一步只能移动到上、下、左、右相邻格子，不能走对角线，也不能在同一条路径中重复使用某个格子。

起点可以是任意格子，只要存在一条完整匹配的路径就返回 true；所有起点都失败才返回 false。不同尝试之间可以重新使用格子，因此访问限制针对当前路径，不是永久禁用某个位置。

题目保证网格和单词非空，字符都是大小写英文字母，匹配区分大小写。进阶要求通过剪枝减少无效搜索。

解法：回溯搜索相邻字符路径

核心思路

[!blue]

一条路径的下一步取决于当前格子和下一个待匹配字符，适合用回溯逐步扩展。定义 dfs(row, col, idx)：之前的路径已匹配 word[0..idx)，判断从当前格子开始能否匹配剩余部分。先拒绝越界或字符不等的情况；当前字符也匹配且 idx 已到末尾，才算找到完整单词。

如果还要继续，先把当前格子临时改为 #，再尝试四个相邻方向匹配 idx + 1。题目只含英文字母，# 不会与单词字符相等，所以已经使用的格子无法再次进入。返回上一层前恢复原字符，让别的路径仍能使用它。成功分支也先保存结果、恢复现场，再返回，保证输入网格最终不变。

搜索前做两类必要条件检查：单词长度不能超过格子总数；单词中任意字符的需求次数不能超过整个网格的供应次数。代码先统计网格字符频次，再逐个扣除单词所需字符，某个计数变成负数就能直接判定无解。但频次足够并不保证相邻关系满足要求，仍需回溯确认。

还可以减少起点候选：若单词首字符在网格中比尾字符更常见，就反转单词，从更少见的一端搜索。网格的相邻关系是双向的，一条合法路径倒着走仍合法，因此反向搜索与原问题等价。比较使用扣除单词需求之前的网格频次；这只是减少搜索的策略，不改变最坏复杂度。

解题步骤

单词长度超过格子总数时直接返回 false；否则统计网格中各字符出现次数。

用原始频次比较单词首尾字符，记录是否应反向搜索；随后逐个扣除单词需要的字符，出现负数立即返回 false。

必要时反转单词，再枚举每个格子，调用 dfs(row, col, 0) 尝试作为起点。

DFS 先判坐标边界，再比较当前字符。字符匹配且已到单词末尾时返回 true。

否则保存并标记当前字符，搜索四个相邻格子，匹配下一个字符；保存搜索结果，恢复当前格子后返回。

任意起点成功即可结束；全部失败返回 false。

代码实现

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

        int[] counts = new int[128];
        for (char[] row : board) {
            for (char ch : row) {
                counts[ch]++;
            }
        }
        boolean reverse = counts[word.charAt(0)] > counts[word.charAt(word.length() - 1)];
        for (int i = 0; i < word.length(); i++) {
            if (--counts[word.charAt(i)] < 0) {
                return false;
            }
        }
        if (reverse) {
            word = new StringBuilder(word).reverse().toString();
        }

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

        return false;
    }

    private boolean dfs(char[][] board, String word, int row, int col, int idx) {
        if (row < 0 || row == board.length || col < 0 || col == board[0].length) {
            return false;
        }

        if (board[row][col] != word.charAt(idx)) {
            return false;
        }

        if (idx == word.length() - 1) {
            return true;
        }

        char origin = board[row][col];

        // 只屏蔽当前路径已使用的格子，其他路径仍可使用。
        board[row][col] = '#';
        boolean found =
                dfs(board, word, row - 1, col, idx + 1)
                        || dfs(board, word, row + 1, col, idx + 1)
                        || dfs(board, word, row, col - 1, idx + 1)
                        || dfs(board, word, row, col + 1, idx + 1);

        // 无论成功还是失败，都先恢复现场再返回结果。
        board[row][col] = origin;

        return found;
    }
}

func exist(board [][]byte, word string) bool {
    if len(word) > len(board)*len(board[0]) {
        return false
    }
    var counts [128]int
    for _, row := range board {
        for _, ch := range row {
            counts[ch]++
        }
    }
    reverse := counts[word[0]] > counts[word[len(word)-1]]
    for i := 0; i < len(word); i++ {
        counts[word[i]]--
        if counts[word[i]] < 0 {
            return false
        }
    }
    if reverse {
        letters := []byte(word)
        for left, right := 0, len(letters)-1; left < right; left, right = left+1, right-1 {
            letters[left], letters[right] = letters[right], letters[left]
        }
        word = string(letters)
    }
    for i := 0; i < len(board); i++ {
        for j := 0; j < len(board[0]); j++ {
            if dfsWord(board, word, i, j, 0) {
                return true
            }
        }
    }
    return false
}

func dfsWord(board [][]byte, word string, row int, col int, idx int) bool {
    if row < 0 || row == len(board) || col < 0 || col == len(board[0]) {
        return false
    }
    if board[row][col] != word[idx] {
        return false
    }
    if idx == len(word)-1 {
        return true
    }

    origin := board[row][col]
    // 只屏蔽当前路径已使用的格子，其他路径仍可使用。
    board[row][col] = '#'
    found := dfsWord(board, word, row-1, col, idx+1) ||
        dfsWord(board, word, row+1, col, idx+1) ||
        dfsWord(board, word, row, col-1, idx+1) ||
        dfsWord(board, word, row, col+1, idx+1)
    // 无论成功还是失败，都先恢复现场再返回结果。
    board[row][col] = origin
    return found
}

复杂度分析

时间复杂度：$O(mn+L+mn\cdot 3^L)$，通常记为 $O(mn\cdot 3^L)$。L 是单词长度，统计与频次剪枝为 $O(mn+L)$；起点有 $mn$ 个，第一步至多四个方向，之后来路已标记，每层至多三个有效方向。剪枝和反向搜索减少实际尝试，不改变最坏指数级上界。

空间复杂度：$O(L)$。字符频次数组大小固定，递归栈深度至多为 L；反转单词需要的字符存储同样为 $O(L)$，无需额外的网格访问数组。

关键点总结

[!green]

回溯状态包含当前位置、待匹配下标，以及网格标记表示的当前已走路径。

访问标记只在当前路径内有效，成功和失败返回前都要恢复。

字符频次不足可以直接判无解，频次足够仍需要检查路径连通顺序。

从较少见的端点开始搜索不改变问题答案，只是缩小候选起点。

易错点总结

[!yellow]

先读格子再判边界，从边缘向外搜索时会越界；字符比较必须在坐标有效后进行。

当前字符还未比较就判断已到单词末尾，会把最后一个字符不匹配的路径也算成功。

把访问标记保留到其他起点，或在成功时直接返回而不恢复，会污染后续搜索或修改输入。

统计次数足够就返回成功，忽略了字符必须按顺序相邻以及不能复用格子的限制。

扣减频次后才用剩余次数比较首尾，比较的就不再是原网格中的起点数量；应提前记录反转选择。

搜索对角线，或者只标记字符值而不是格子位置，都不符合题目的路径规则。

相似题目

题目	难度	关联与区别
212. 单词搜索 II	困难	从查找一个单词扩展为多个单词，Trie能共享相同搜索前缀。
200. 岛屿数量	中等	同样在网格上DFS，本题的访问标记只对当前路径有效，回溯时必须恢复。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

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

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！