type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
输入为一个
m x n的二维字符网格board,一个字符串单词word。如果
word存在于网格中,返回 true;否则,返回false。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“ 相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例1:

示例2:
%E5%9B%BE%E7%89%87_1.png?table=block&id=2af8aa42-a804-8088-baf7-f9c4be63d46e&t=2af8aa42-a804-8088-baf7-f9c4be63d46e)
示例3:
%E5%9B%BE%E7%89%87_2.png?table=block&id=2af8aa42-a804-80e5-879c-f3f0041b1c99&t=2af8aa42-a804-80e5-879c-f3f0041b1c99)
说明:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board和word仅由大小写英文字母组成
解法一:回溯
从每个与
word[0] 相等的起点出发,做DFS。沿路匹配字符,临时把当前格子标记为“已用”(如改成特殊值),回溯时再还原,避免额外
visited 集合的开销。复杂度
- 时间:最坏
O(m*n*4^L),L=len(word);通常远小于最坏。
- 空间:
O(L)递归深度。
解法二:回溯 + 计数剪枝 + 起点过滤
- 全局字符计数剪枝:若棋盘里某个字母的出现次数少于
word中对应字母的次数,直接返回False。
- 起点过滤:只从
board[i][j] == word[0]的格子启动 DFS(减少入口)。
- 其余与解法一相同。
复杂度
- 时间:计数预处理
O(m*n);DFS 同解法一的上界,但入口更少、早停更多,均摊更快。
- 空间:
O(L)。
解法三:回溯 + 强剪枝
在解法二基础上加入两类常用强剪枝:
- 稀有端优先(Rarity Heuristic):统计
word两端字符在棋盘上的频次,从出现更少的一端开始搜索;若是末端更稀有,就把word反转。这样能大幅降低搜索树早期的分支数。
- 可达性/上界剪枝:在 DFS 中,若剩余字符数大于“在不重复格子的前提下还能走到的最大步数”,直接返回
False。简化版可用局部访问上界(如:从当前位置最多还剩m*n未访问格,但通常不必在 LC79 实现最强形式—会增大常数)。
复杂度
- 时间:最坏同上,但实际平均耗时显著降低(首字母稀有化让大量起点直接剪去)。
- 空间:
O(L)。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-79-单词搜索
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 62] 不同路径
下一篇
[Leetcode 83] 删除排序链表中的重复元素