当前位置: 首页 > ai >正文

【LeetCode 热题 100】79. 单词搜索——回溯

Problem: 79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

文章目录

  • 整体思路
  • 完整代码
  • 时空复杂度
    • 时间复杂度:O(M * N * 3^L)
    • 空间复杂度:O(L)

整体思路

这段代码旨在解决一个经典的二维网格搜索问题:单词搜索 (Word Search)。其核心功能是判断一个给定的单词 word 是否存在于一个字符网格 board 中。构成单词的路径规则是:字母必须在网格中水平或垂直相邻,并且同一个单元格的字母在路径中不允许被重复使用。

该算法采用了 深度优先搜索(DFS) 结合 回溯(Backtracking) 的策略。其整体思路可以分解为以下几个步骤:

  1. 主驱动逻辑(遍历所有起点)

    • exist 方法是算法的入口。它通过两层嵌套的 for 循环遍历网格 board 中的每一个单元格 (i, j)
    • 这个遍历的目的是将每一个单元格都视作单词 word 的一个潜在 起始点
    • 对于每一个起点,它都会调用核心的 dfs 辅助函数来尝试进行深度搜索。如果任何一次 dfs 调用返回 true,意味着找到了完整的单词路径,程序立即返回 true
    • 如果遍历完所有可能的起点后,dfs 均未成功,则说明单词不存在于网格中,程序最后返回 false
  2. 核心搜索逻辑(DFS 与回溯)

    • dfs(i, j, k, ...) 是一个递归函数,负责从单元格 (i, j) 开始,尝试匹配 word 中从第 k 个字符开始的剩余部分。
    • 剪枝与基准情况
      • 失败剪枝:如果当前单元格 (i, j) 超出边界(在递归调用前检查),或者其字符 board[i][j] 与目标字符 word[k] 不匹配,则此路不通,直接返回 false
      • 成功基准:如果当前字符匹配,并且这已经是单词的最后一个字符(k == word.length - 1),则说明整个单词已经成功匹配,返回 true
    • 递归与回溯
      • 标记(Marking):为了防止在同一路径中重复使用单元格,在深入探索之前,代码会将当前单元格 board[i][j] 的值临时修改为一个特殊标记(如此代码中的 0)。这相当于一个“正在访问”的标记。
      • 探索(Exploration):接着,代码会向当前单元格的四个相邻方向(上、下、左、右)进行递归调用 dfs(x, y, k + 1, ...),尝试匹配单词的下一个字符。
      • 回溯(Backtracking):在四个方向的递归探索完成之后(无论成功还是失败),必须将当前单元格 board[i][j] 的值恢复为其原始字符 word[k]。这是回溯算法的精髓,它确保了在探索其他起始点的路径时,该单元格是可用的。
      • 如果四个方向的探索都没有找到完整的路径,则从当前点出发的搜索失败,返回 false

完整代码

class Solution {// 定义一个常量数组,用于表示四个方向的坐标偏移量:右、左、下、上private static final int[][] DIRECTION = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};/*** 在二维字符网格中查找是否存在一个给定的单词。* @param board 二维字符网格* @param word  要查找的单词* @return 如果单词存在,返回 true;否则,返回 false。*/public boolean exist(char[][] board, String word) {// 将目标单词转换为字符数组,以提高后续字符访问的效率char[] w = word.toCharArray();// 遍历网格中的每一个单元格,将其作为单词搜索的潜在起点for (int i = 0; i < board.length; i++) {for (int j = 0; j < board[0].length; j++) {// 从 (i, j) 开始进行深度优先搜索,尝试匹配单词的第一个字符 (k=0)if (dfs(i, j, 0, board, w)) {// 如果找到了一个完整的路径,立即返回 truereturn true;}}}// 如果遍历完所有可能的起点都未能找到单词,则返回 falsereturn false;}/*** 深度优先搜索辅助函数。* @param i      当前搜索的行索引* @param j      当前搜索的列索引* @param k      当前要匹配的目标单词中的字符索引* @param board  字符网格* @param word   目标单词的字符数组* @return 如果从 (i, j) 出发能找到 word[k...] 的路径,返回 true*/private boolean dfs(int i, int j, int k, char[][] board, char[] word) {// 剪枝:如果当前单元格的字符与目标字符不匹配,此路不通if (board[i][j] != word[k]) {return false;}// 成功基准:如果当前字符匹配,并且已是单词的最后一个字符,则搜索成功if (k == word.length - 1) {return true;}// 关键【标记】步骤:将当前单元格标记为已访问,防止在同一路径中重复使用。// 这里用一个非字符值(如0)来标记,也可以用一个不会在 board 和 word 中出现的特殊字符。board[i][j] = 0; // 探索四个相邻的方向for (int[] dir : DIRECTION) {int x = dir[0] + i;int y = dir[1] + j;// 检查新坐标 (x, y) 是否在网格边界内if (x >= 0 && x < board.length && y >= 0 && y < board[0].length) {// 对有效的相邻单元格进行递归调用,尝试匹配单词的下一个字符 (k+1)if (dfs(x, y, k + 1, board, word)) {// 如果任意方向的递归探索成功,立即返回 truereturn true;}}}// 关键【回溯】步骤:恢复当前单元格的原始值。// 这样,在回溯到上一个状态后,其他分支的搜索路径仍然可以使用此单元格。board[i][j] = word[k];// 如果所有方向都探索完毕,仍未找到匹配路径,则返回 falsereturn false;}
}

时空复杂度

时间复杂度:O(M * N * 3^L)

  1. 外层循环exist 方法中的两层 for 循环遍历了整个网格,这部分是 M * N 次操作,其中 M 是行数,N 是列数。
  2. DFS 复杂度:对于每个起点,都会调用 dfs 函数。在 dfs 函数中,每次递归都会向最多 3 个新的方向探索(因为不能走回头路,而修改 board 值的操作天然地防止了这一点)。
  3. 递归深度:递归的最大深度由单词的长度 L 决定。
  4. 综合分析
    • 在最坏的情况下,对于网格中的每个单元格 (M * N),我们都可能启动一次深度优先搜索。
    • 每次搜索的计算量大致可以估算为 3^L,因为每一步都有最多3个选择,持续 L 步。
    • 因此,总的时间复杂度是一个粗略的上限:O(M * N * 3^L),其中 L 是单词 word 的长度。

空间复杂度:O(L)

  1. 主要存储开销:算法的额外空间开销主要来自于递归调用栈。
  2. 递归深度dfs 函数的递归深度取决于正在匹配的单词的长度。在最坏的情况下,当成功匹配到单词的最后一个字母时,递归栈的深度会达到 L
  3. 其他变量
    • w = word.toCharArray(): 占用了 O(L) 的空间。
    • DIRECTION 数组:占用 O(1) 的常数空间。
    • 递归函数中的局部变量:占用 O(1) 空间。

综合分析
递归栈的深度是空间复杂度的主要部分。因此,算法的空间复杂度为 O(L),其中 L 是单词 word 的长度。

参考灵神

http://www.xdnf.cn/news/16284.html

相关文章:

  • 电子电气架构 --- 车载软件交样评审流程
  • Java面试题及详细答案120道之(041-060)
  • 排序算法,咕咕咕
  • 进制定义与转换详解
  • vcpkg如何交叉编译
  • HCLP--MGER综合实验
  • 数据结构习题--删除排序数组中的重复项
  • 详解力扣高频SQL50题之1084. 销售分析 III【简单】
  • Python点阵字生成与优化:从基础实现到高级渲染技术
  • 数据恢复与备份
  • 快速入门Linux操作系统(一)
  • 立式加工中心X-Y轴传动机械结构设“cad【6张】三维图+设计说明书
  • 进阶数据结构:用红黑树实现封装map和set
  • 学习嵌入式的第三十一天-数据结构-(2025.7.23)网络协议封装
  • 数据中心-时序数据库InfluxDB
  • 掌握Gemini-2.5:现代AI开发中实用应用的综合指南
  • 二次函数图像动画展示
  • 在Power Automate Desktop中执行PowerShell获取SharePoint online某个文件夹的用户权限列表
  • excel删除重复项场景
  • 算法竞赛阶段二-数据结构(35)数据结构单链表模拟实现
  • Node.js 模拟 Linux 环境
  • 【每天一个知识点】GAN(生成对抗网络,Generative Adversarial Network)
  • Whisper语音转文字
  • 【洛谷】单向链表、队列安排、约瑟夫问题(list相关算法题)
  • 互联网应用主流框架整合 Spring Boot开发
  • Linux DNS 服务器正反向解析
  • 【IMMCKF】基于容积卡尔曼滤波(CKF)的多模型交互的定位程序,模型为CV和CT,三维环境,matlab代码|附下载链接
  • Nestjs框架: 基于Mongodb的多租户功能集成和优化
  • 算子推理是什么
  • 电脑开机后网络连接慢?