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

可视化图解算法63:单词搜索

LeetCode 79. 单词搜索

1. 题目

描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中,返回 true ;否则,返回 false

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1:

word-2

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true

示例 2:

word-1

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true

示例 3:

word-3

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出:false

提示:

  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • boardword 仅由大小写英文字母组成

2. 解题思路

通过回溯实现单词的搜索。

回溯算法模板

63-1

如果文字描述的不太清楚,你可以参考视频的详细讲解。

  • Python版本:https://www.bilibili.com/cheese/play/ep1374923
  • Java版本:https://www.bilibili.com/cheese/play/ep1368187
  • Golang版本:https://www.bilibili.com/cheese/play/ep1365129

3. 编码实现

核心代码如下:

var (row, column intvisited     [][]bool
)func exist(board [][]byte, word string) bool {row = len(board)column = len(board[0])visited = make([][]bool, row)for i := 0; i < row; i++ {visited[i] = make([]bool, column)}// 遍历二维网格的每一个点,作为搜索的起点for i := 0; i < row; i++ {for j := 0; j < column; j++ {if backtracking(board, word, i, j, 0) {return true}}}return false
}
func backtracking(board [][]byte, word string, i int, j int, index int) bool {//字符不相等,直接返回if !isValid(i, j) || board[i][j] != word[index] {return false}//3. 剪枝:如果字符已访问,直接返回if visited[i][j] {return false}//2.递归终止条件: 如果当前字符是字符串的最后一个字符,则找到了匹配项if index == len(word)-1 {return true}//1.选择:在本层集合中遍历元素//1.1 处理节点( 标记当前位置为已访问)visited[i][j] = true// 1.2 递归( 递归地在四个方向搜索)//向左if backtracking(board, word, i-1, j, index+1) {return true}//向右if backtracking(board, word, i+1, j, index+1) {return true}//向上if backtracking(board, word, i, j-1, index+1) {return true}//向下if backtracking(board, word, i, j+1, index+1) {return true}//1.3 回溯,撤销选择(将当前位置标记为未访问)visited[i][j] = falsereturn false
}func isValid(i int, j int) bool {return (i >= 0 && i < row) && (j >= 0 && j < column)
}

具体完整代码你可以参考下面视频的详细讲解。

  • Python版本:https://www.bilibili.com/cheese/play/ep1374923
  • Java版本:https://www.bilibili.com/cheese/play/ep1368187
  • Golang版本:https://www.bilibili.com/cheese/play/ep1365129

4.小结

通过回溯实现单词搜索。步骤:二维网格的每一个点作为搜索的起点,搜索的时候采用回溯方法。1)将当前网格点设置为已访问过;2)到当前点的上、下、左、右四个方向递归尝试;3)回溯,撤销选择,即将当前网格点设置为未访问。

分割线

《数据结构与算法》深度精讲课程正式上线啦!7 大核心算法模块全解析:

  ✅   链表

  ✅   二叉树

  ✅   二分查找、排序

  ✅   堆、栈、队列

  ✅   回溯算法

  ✅   哈希算法

  ✅   动态规划

无论你是备战笔试面试、提升代码效率,还是突破技术瓶颈,这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡,与千名开发者共同进阶!

  • Python编码实现:https://www.bilibili.com/cheese/play/ss897667807
  • Java编码实现:https://www.bilibili.com/cheese/play/ss161443488
  • Golang编码实现:https://www.bilibili.com/cheese/play/ss63997

对于LeetCode数据结构与算法,我们总结了一套【可视化+图解】方法,依据此方法来解决相关问题,算法变得易于理解,写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句:老骥伏枥,志在千里;烈士暮年,壮心不已。

http://www.hskmm.com/?act=detail&tid=28048

相关文章:

  • Playwright MCP在UI回归测试中的实战:构建AI自主测试智能体
  • 基于多平台协同的芯片制造数据治理体系架构与实践
  • 华为设备实现单臂路由
  • vscode中配置c_c++环境
  • Playwright MCP 浏览器自动化框架全面解析
  • Spring中使用Apache Http客户端调第三方系统接口临时查看请求体参数 - 指南
  • vscode 设置c/c++代码格式化插件
  • Microsoft.AspNetCore.Builder
  • 【往届已检索|EI稳定检索】第五届信息技术与当代体育国际学术会议(TCS 2025)
  • windows版本 中间件更新问题记录
  • AI大模型应用实践 八:如何通过RAG数据库实现大模型的私有化定制与优化
  • 【完结11章】基于Golang+Gin+Gorm+Vue3母婴商城项目实战
  • 25-1010 从房间回声看懂离散卷积原理
  • 如何设计10亿用户级的微博Feed流系统并应对100W QPS的挑战?
  • 印度尼西亚股票实时数据API对接文档
  • 2025 年铝门窗厂家推荐榜,系统 / 智能 / 断桥 / 窄边 / 定制 / 全景 / 阳光房 / 隐框 / 隔声 / 防火铝门窗公司推荐
  • 如何播放 M3U8 格式的视频
  • 20232304 2025-2026-1 《网络与系统攻防技术》实验一实验报告
  • Codeforces Round 1056 (Div. 2) A~D
  • 现代软件工程阅读和提问作业-1
  • 一种CDN动态加速回源白名单选路及降低源站探测量的方法
  • Windows系统-应用问题全面剖析Ⅰ:德承工控机DA-1200在Windows操作系统下[开机黑屏]的解决方法 - Johnny
  • 某中心在旧金山设立AGI实验室专注长期AI研究
  • Appcrawler自动遍历工具-智能遍历测试与测试用例生成
  • [USACO20FEB] Clock Tree S
  • 光储充一体化 + MyEMS:新能源场站的 “能源管家” 是这样工作的
  • idea插件Doc View
  • PGSQL + patroni + timescaledb 集群搭建
  • 随着种植精细化需求提升,草莓滴灌管、圆柱式滴灌管及 PVC 滴灌管成为节水灌溉核心装备,盘点五家实力厂家的特色产品
  • 2025 年最新推荐 OCR 图片识别软件厂商榜单:全面解析文字识别与格式转换服务商技术实力及服务能力ocr图片转excel/ocr图片转word厂商推荐