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

算法leetcode|79. 单词搜索(rust重拳出击)


文章目录

  • 79. 单词搜索:
    • 样例 1:
    • 样例 2:
    • 样例 3:
    • 提示:
    • 进阶:
  • 分析:
  • 题解:
    • rust:
    • go:
    • c++:
    • python:
    • java:


79. 单词搜索:

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

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

样例 1:

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

样例 2:

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

样例 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
  • board 和 word 仅由大小写英文字母组成

进阶:

  • 你可以使用搜索剪枝的技术来优化解决方案,使其在 board 更大的情况下可以更快解决问题?

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。
  • 需要尝试所有的可能,遍历是不可少的,使用循环或者递归,递归是首选,因为比较容易实现,深度优先,回溯,递归套娃大法好。
  • 需要遍历每一个元素,然后开始从每个位置使用递归套娃大法,分别向上,下,左,右四个方向进行递归,重复操作,直到匹配成功,或者匹配失败就回溯尝试其他,需要注意的是不走重复的位置,所以需要一个结构标记已经走过的位置,使用和原二维字符网格相同大小的结构比较容易,空间上应该还可以优化,但是没有深究,因为空间上并没有浪费,如果做优化,肯定是以牺牲效率为代价,所谓时间换空间,我不要换。

题解:

rust:

impl Solution {pub fn exist(board: Vec<Vec<char>>, word: String) -> bool {fn check(board: &Vec<Vec<char>>, word: &Vec<char>, idx: usize, visited: &mut Vec<Vec<bool>>, r: usize, c: usize) -> bool {if r >= visited.len() || c >= visited[0].len() || visited[r][c] || board[r][c] != word[idx] {return false;}if idx == word.len() - 1 {// 完全匹配return true;}visited[r][c] = true;// 上下左右递归套娃大法if check(board, word, idx + 1, visited, r - 1, c)|| check(board, word, idx + 1, visited, r + 1, c)|| check(board, word, idx + 1, visited, r, c - 1)|| check(board, word, idx + 1, visited, r, c + 1){return true;}visited[r][c] = false;return false;}let word = word.chars().collect::<Vec<_>>();let mut visited = vec![vec![false; board[0].len()]; board.len()];for r in 0..board.len() {for c in 0..board[0].len() {if check(&board, &word, 0, &mut visited, r, c) {return true;}}}return false;}
}

go:

func exist(board [][]byte, word string) bool {visited := make([][]bool, len(board))for i := range visited {visited[i] = make([]bool, len(board[0]))}var check func(idx, r, c int) boolcheck = func(idx, r, c int) bool {if r < 0 || r >= len(board) || c < 0 || c >= len(board[0]) || visited[r][c] || board[r][c] != word[idx] {return false}if idx == len(word)-1 {// 完全匹配return true}visited[r][c] = true// 上下左右递归套娃大法if check(idx+1, r-1, c) || check(idx+1, r+1, c) || check(idx+1, r, c-1) || check(idx+1, r, c+1) {return true}visited[r][c] = falsereturn false}for r, row := range board {for c := range row {if check(0, r, c) {return true}}}return false
}

c++:

class Solution {
private:bool check(vector<vector<char>>& board, string& word, int idx, vector<vector<bool>>& visited, int r, int c) {if (r < 0 || r >= visited.size() || c < 0 || c >= visited[0].size() || visited[r][c] || board[r][c] != word[idx]) {return false;}if (idx == word.size() - 1) {// 完全匹配return true;}visited[r][c] = true;// 上下左右递归套娃大法if (check(board, word, idx + 1, visited, r - 1, c)|| check(board, word, idx + 1, visited, r + 1, c)|| check(board, word, idx + 1, visited, r, c - 1)|| check(board, word, idx + 1, visited, r, c + 1)) {return true;}visited[r][c] = false;return false;}
public:bool exist(vector<vector<char>>& board, string word) {vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));for (int r = 0; r < board.size(); ++r) {for (int c = 0; c < board[0].size(); ++c) {if (check(board, word, 0, visited, r, c)) {return true;}}}return false;}
};

python:

class Solution:def exist(self, board: List[List[str]], word: str) -> bool:def check(idx: int, r: int, c: int) -> bool:if r < 0 or r >= len(board) or c < 0 or c >= len(board[0]) or visited[r][c] or board[r][c] != word[idx]:return Falseif idx == len(word) - 1:return Truevisited[r][c] = Trueif check(idx + 1, r - 1, c) or check(idx + 1, r + 1, c) or check(idx + 1, r, c - 1) or check(idx + 1, r, c + 1):return Truevisited[r][c] = Falsereturn Falsevisited = [[False] * len(board[0]) for _ in range(len(board))]for r in range(len(board)):for c in range(len(board[0])):if check(0, r, c):return Truereturn False

java:

class Solution {public boolean exist(char[][] board, String word) {boolean[][] visited = new boolean[board.length][board[0].length];for (int r = 0; r < board.length; ++r) {for (int c = 0; c < board[0].length; ++c) {if (check(board, word, 0, visited, r, c)) {return true;}}}return false;}private boolean check(char[][] board, String word, int idx, boolean[][] visited, int r, int c) {if (r < 0 || r >= visited.length || c < 0 || c >= visited[0].length || visited[r][c] || board[r][c] != word.charAt(idx)) {return false;}if (idx == word.length() - 1) {// 完全匹配return true;}visited[r][c] = true;// 上下左右递归套娃大法if (check(board, word, idx + 1, visited, r - 1, c)|| check(board, word, idx + 1, visited, r + 1, c)|| check(board, word, idx + 1, visited, r, c - 1)|| check(board, word, idx + 1, visited, r, c + 1)) {return true;}visited[r][c] = false;return false;}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~


相关文章:

算法leetcode|79. 单词搜索(rust重拳出击)

文章目录 79. 单词搜索&#xff1a;样例 1&#xff1a;样例 2&#xff1a;样例 3&#xff1a;提示&#xff1a;进阶&#xff1a; 分析&#xff1a;题解&#xff1a;rust&#xff1a;go&#xff1a;c&#xff1a;python&#xff1a;java&#xff1a; 79. 单词搜索&#xff1a; …...

2023年高教社杯全国大学生数学建模竞赛参赛事项注意

MathClub数模资源&#xff0c;含专属思路 资源链接&#xff1a;点击这里获取众多数模资料、思路精讲、论文模板latex和word、学习书籍等 2023高教社杯数学建模国赛–赛前准备 一年一度的数学建模国赛要来啦&#xff01;&#xff01;&#xff01;小编仔细阅读了比赛官方网站上…...

数学建模--逻辑回归算法的Python实现

首先感谢CSDN上发布吴恩达的机器学习逻辑回归算法任务的各位大佬. 通过大佬的讲解和代码才勉强学会. 这篇文章也就是简单记录一下过程和代码. CSDN上写有关这类文章的大佬有很多,大家都可以多看一看学习学习. 机器学习方面主要还是过程和方法. 这篇文章只完成了线性可分方面的任…...

Qt6_贪吃蛇Greedy Snake

贪吃蛇Greedy Snake 1分析 首先这是一个贪吃蛇界面&#xff0c;由一个长方形边框和一只贪吃蛇组成 默认开局时&#xff0c;贪吃蛇身体只有3个小方块&#xff0c;使用画笔画出 1.1如何移动 对于蛇的移动&#xff0c;有2种方法 在一定时间范围内(定时器)&#xff0c;未对游戏…...

Credo推出业界首款单片集成CMOS VCSEL驱动器的800G光DSP芯片

针对AOC及短距&#xff08;SR&#xff09;光模块优化的新型Credo DSP&#xff0c;适用于下一代超大规模数据中心/AI应用 加州圣何塞和中国深圳&#xff0c;2023年9月6日——Credo Technology&#xff08;纳斯达克股票代码&#xff1a;CRDO&#xff09;今日发布两款新品&#x…...

【经验分享】如何使用VSCode对比两个文件

问题&#xff1a; 当有两个不同版本的文件&#xff0c;如何使用VSCode对比两个文件 解决办法 长按ctrl选择想要对比的两个文件-----右键选择将已选项进行比较----大功告成 大功告成...

从裸机开始安装ubuntu系统到安装NVIDIA驱动

这篇文章为总结类文章&#xff0c;更多的是把各个博主的内容总结一下&#xff0c;形成一套端到端的方法&#xff0c;主要内容包括&#xff1a; 安装ubuntu22.04版本(含启动U盘制作)配置ssh、固定ip和端口号安装NVIDIA驱动安装cuda11.7和cudnn8.6 文章目录 一、安装ubuntu22.041…...

索尼 toio™ 应用创意开发征文|小巧机器,大无限,探索奇妙世界

文章目录 前言微型机器人的未来&#xff1a;toio™小机器人简介toio™小机器人&#xff1a;创新功能一览toio™小机器人&#xff1a;多领域的变革者toio™小机器人贪吃蛇游戏代码实现写在最后 前言 当我们谈到现代科技的创新时&#xff0c;往往会联想到复杂的机器和高级的编程…...

什么牌子的led台灯质量好?热门的Led护眼台灯推荐

led台灯有环保无污染、耗能低、长寿命等优点&#xff0c;适合用在阅读、书写、批阅等办公或学习的场所。而挑选LED台灯时&#xff0c;分散光挡板做的比较好的优先选择&#xff0c;能分散大量蓝光&#xff0c;对眼睛危害较小。下面&#xff0c;小编为大家推荐五款质量好的led护眼…...

预推免,保研------长安大学保内,附加分面试准备【记录帖】

&#x1f680;长安大学——人工智能系——程惠泽 &#x1f68c;前六学期专业排名&#xff1a;7/82 &#x1f68c;信息门户GPA&#xff1a;3.94 &#x1f68c;平均成绩&#xff1a;89.83 &#x1f68c;加权成绩&#xff1a;89.15 / ☁️本人比较菜&#xff0c;只能保研本校&…...

Linux开源防病毒引擎ClamAV

ClamAV官方地址&#xff1a;https://www.clamav.net 它支持Linux、BSD、windows、Mac OS X等系统。 在CentOS 8&#xff08;Tencent OS 3.1&#xff09;安装非常便利&#xff0c;可以使用yum。 yum install clamav 安装成功&#xff0c;就可以使用它进行病毒扫描检查了。 c…...

Java复习-25-单例设计模式

单例设计模式 目的&#xff08;使用场景&#xff09; 在实际开发下&#xff0c;会存在一种情况&#xff1a;某一种类在程序的整个生命周期中&#xff0c;只需要实例化一次就足够了。例如&#xff0c;系统数据类&#xff0c;由于操作系统只有一个&#xff0c;因此在程序初始化…...

博客系统自动化测试项目实战(测试系列9)

目录 前言&#xff1a; 1.博客前端页面测试用例图 2.测试用例的代码实现 2.1登录页面的测试 2.2博客列表页面的测试 2.3写博客测试 2.4博客详情页面的测试 2.5已发布博客的标题和时间的测试 2.6注销用户的测试 结束语&#xff1a; 前言&#xff1a; 之前小编给大家讲…...

华纳云:Linux的底层体系结构是怎样的

Linux操作系统的底层体系结构是一个开源的Unix-like操作系统内核&#xff0c;通常称为Linux内核(Linux Kernel)。下面是Linux底层体系结构的主要组成部分和工作原理&#xff1a; 内核&#xff08;Kernel&#xff09;&#xff1a; Linux的核心部分是内核&#xff0c;它是操作系统…...

SpringMVC常用注解介绍及参数传递说明

前言 上一篇文章介绍了SpringMVC是什么以及它的工作流程和核心组件&#xff0c;介绍入门示例时&#xff0c;提到了RequestMapping注解&#xff0c;那么这篇文章就来介绍SpringMVC中更多的常用的注解&#xff0c;以及它的参数传递。 一. SpringMVC常用注解 1.1 RequestParam …...

4 个你可能不知道的 Python 迭代工具过滤器函数

推荐&#xff1a;使用 NSDT场景编辑器 快速搭建3D应用场景 当您只想循环遍历迭代器、检索序列中的元素并处理它们时&#xff0c;这些元素特别有用 - 所有这些都无需将它们存储在内存中。今天我们将学习如何使用以下四个迭代工具过滤器函数&#xff1a; filterfalsetakewhiledr…...

Scrapy简介-快速开始-项目实战-注意事项-踩坑之路

scrapy项目模板地址&#xff1a;https://github.com/w-x-x-w/Spider-Project Scrapy简介 Scrapy是什么&#xff1f; Scrapy是一个健壮的爬虫框架&#xff0c;可以从网站中提取需要的数据。是一个快速、简单、并且可扩展的方法。Scrapy使用了异步网络框架来处理网络通讯&…...

lightdb 支持兼容Oracle的to_clob函数

文章目录 概述案例演示 概述 在信创移植的SQL语句中&#xff0c;有来源于Oracle数据库的SQL语句。 在ORACLE PL/SQL包中&#xff0c;你可以使用TO_CLOB(character)函数将RAW、CHAR、VARCHAR、VARCHAR2、NCHAR、NVARCHAR2、CLOB值转换为CLOB。 因此在LightDB 23.3版本中实现了…...

ES6中let和const关键字与var关键字之间的区别?

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ 变量作用域&#xff08;Scope&#xff09;&#xff1a;⭐ 变量提升&#xff08;Hoisting&#xff09;&#xff1a;⭐ 重复声明&#xff1a;⭐ 初始化&#xff1a;⭐ 全局对象属性&#xff1a;⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#…...

Python中的异常处理3-1

Python中的异常指的是语法上没有错误&#xff0c;但是代码执行时会导致错误的情况。 1 抛出异常 在图1所示的代码中&#xff0c;要求用户输入一个数字&#xff0c;该代码在语法上没有错误。 图1 出现异常的代码 但是运行该代码之后&#xff0c;如果用户输入的是数字&#xf…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...