[Leetcode 79] 单词搜索

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
输入为一个m x n的二维字符网格board,一个字符串单词word
如果word存在于网格中,返回 true;否则,返回false。
 
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“ 相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 
示例1:
notion image
示例2
notion image
 
示例3:
notion image
 
说明:
  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • boardword 仅由大小写英文字母组成
 

解法一:回溯

从每个与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)

解法三:回溯 + 强剪枝

在解法二基础上加入两类常用强剪枝:
  1. 稀有端优先(Rarity Heuristic):统计 word 两端字符在棋盘上的频次,从出现更少的一端开始搜索;若是末端更稀有,就把 word 反转。这样能大幅降低搜索树早期的分支数。
  1. 可达性/上界剪枝:在 DFS 中,若剩余字符数大于“在不重复格子的前提下还能走到的最大步数”,直接返回 False。简化版可用局部访问上界(如:从当前位置最多还剩 m*n 未访问格,但通常不必在 LC79 实现最强形式—会增大常数)。
复杂度
  • 时间:最坏同上,但实际平均耗时显著降低(首字母稀有化让大量起点直接剪去)。
  • 空间:O(L)
上一篇
[Leetcode 62] 不同路径
下一篇
[Leetcode 83] 删除排序链表中的重复元素