LeetCode刷题--- 单词搜索

个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

 http://t.csdnimg.cn/yUl2I

【C++】    

​​​​​​http://t.csdnimg.cn/6AbpV

数据结构与算法

 ​​​​http://t.csdnimg.cn/hKh2l


前言:这个专栏主要讲述递归递归、搜索与回溯剪枝算法,所以下面题目主要也是这些算法做的  

我讲述题目会把讲解部分分为3个部分:
1、题目解析

2、算法原理思路讲解

3、代码实现


单词搜索

题目链接:单词搜索

题目

给定一个 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 仅由大小写英文字母组成

解法

题目解析

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

算法原理思路讲解

我们需要假设每个位置的元素作为第⼀个字⺟,然后向相邻的四个⽅向进⾏递归,并且不能出现重复使⽤同⼀个位置的元素。通过深度优先搜索的⽅式,不断地枚举相邻元素作为下⼀个字⺟出现的可能性,并在递归结束时回溯,直到枚举完所有可能性,得到正确的结果。
一、画出决策树

 


二、设计代码

(1)全局变量

string Word;
bool visit[10][16];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
  • Word(word的值)
  • visit(二位数组中的元素是否被用过)
  • dx[4](用于计算)
  • dy[4](用于计算)

(2)设计递归函数

bool dfs(vector<vector<char>>& board, int row, int col, int pos);
  • 参数:row(当前需要进⾏处理的元素横坐标),col(当前需要进⾏处理的元素横坐标),pos(当前已经处理的元素个数);
  • 返回值:布尔值 ;
  • 函数作用:判断当前坐标的元素作为字符串中下标 step 的元素出现时,向四个⽅向传递,查找是否存在路径结果与字符串相同。

递归过程

  1. 遍历每个位置,标记当前位置并将当前位置的字⺟作为⾸字⺟进⾏递归,并且在回溯时撤回标记。
    1. 在每个递归的状态中,我们维护⼀个步数 pos,表⽰当前已经处理了⼏个字⺟。
    2. 若当前位置的字⺟与字符串中的第 pos 个字⺟不相等,则返回 false。
    3. 若当前 pos 的值与字符串⻓度相等,表⽰存在⼀种路径使得 word 成⽴,返回 true。
  2. 对当前位置的上下左右四个相邻位置进⾏递归,若递归结果为 true,则返回 true。
  3. 若相邻的四个位置的递归结果都为 false,则返回 false。
特别地,如果使⽤将当前遍历到的字符赋值为空格,并在回溯时恢复为原来的字⺟的⽅法,则在递归时不会重复遍历当前元素,可达到不使⽤标记数组的⽬的。

代码实现

class Solution {
public:
string Word;
bool visit[10][16];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };bool dfs(vector<vector<char>>& board, int row, int col, int pos){if (pos == Word.size()){return true;}int m = board.size();int n = board[0].size();for (int i = 0 ; i < 4; i++){ int x = row + dx[i], y = col + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && !visit[x][y] && board[x][y]== Word[pos]){visit[x][y] = true;if (dfs(board, x, y,pos + 1)) return true;visit[x][y] = false;}}return false;}bool exist(vector<vector<char>>& board, string word) {Word = word;for (int i = 0; i < board.size(); i++){for (int j = 0; j < board[i].size(); j++){if (board[i][j] == word[0]){visit[i][j] = true;if (dfs(board, i, j, 1) == true)return true;visit[i][j] = false;;}}}return false;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/227164.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

JavaEE - 网络编程之回显服务器

目录 一.什么是回显服务器&#xff1f; 二.UDP是什么&#xff1f; 1.TCP 是有链接的&#xff0c; UDP 是无连接的 2.TCP是可靠传输的,UDP是不可靠传输的 3.TCP是面向字节流的&#xff0c;UDP是面向数据报 4.TCP和UDP是全双工的 三.UDP的 socket api 四. 具体代码实现 …

C++ Primer Plus----第十二章--类和动态内存分布

本章内容包括&#xff1a;对类成员使用动态内存分配&#xff1b;隐式和显式复制构造函数&#xff1b;隐式和显式重载赋值运算符&#xff1b;在构造函数中使用new所必须完成的工作&#xff1b;使用静态类成员&#xff1b;将定位new运算符用于对象&#xff1b;使用指向对象的指针…

山西电力市场日前价格预测【2023-12-28】

日前价格预测 预测说明&#xff1a; 如上图所示&#xff0c;预测明日&#xff08;2023-12-28&#xff09;山西电力市场全天平均日前电价为814.30元/MWh。其中&#xff0c;最高日前电价为1500.00元/MWh&#xff0c;预计出现在08:00~08:45,17:00~20:15。最低日前电价为394.61元/…

AI人工智能大模型讲师叶梓《基于人工智能的内容生成(AIGC)理论与实践》培训提纲

【课程简介】 本课程介绍了chatGPT相关模型的具体案例实践&#xff0c;通过实操更好的掌握chatGPT的概念与应用场景&#xff0c;可以作为chatGPT领域学习者的入门到进阶级课程。 【课程时长】 1天&#xff08;6小时/天&#xff09; 【课程对象】 理工科本科及以上&#xff0…

elasticsearch 笔记二:搜索DSL 语法(搜索API、Query DSL)

文章目录 一、搜索 API1. 搜索 API 端点地址2. URI Search3. 查询结果说明5. 特殊的查询参数用法6. Request body Search6.1 query 元素定义查询6.2 指定返回哪些内容6.2.1 source filter 对_source 字段进行选择6.2.2 stored_fields 来指定返回哪些 stored 字段6.2.3 docValue…

经典文献阅读之--OccNeRF(基于神经辐射场的自监督多相机占用预测)

0. 简介 作为基于视觉感知的基本任务&#xff0c;3D占据预测重建了周围环境的3D结构。它为自动驾驶规划和导航提供了详细信息。然而&#xff0c;大多数现有方法严重依赖于激光雷达点云来生成占据地面真实性&#xff0c;而这在基于视觉的系统中是不可用的。之前我们介绍了《经典…

苹果Mac电脑甘特图管 EasyGantt最新 for mac

EasyGantt提供直观的界面&#xff0c;让用户能够轻松创建具有时间轴视图的甘特图。你可以添加并排列任务、设置任务的开始和结束日期、调整任务之间的依赖关系等。 任务管理&#xff1a;软件允许你添加、编辑和删除任务&#xff0c;设定任务的优先级和状态&#xff0c;并为每个…

Spring AOP<一>简介与基础使用

spring AOP 基础定义 含义使用切面组织多个Advice,Advice放在切面中定义。也就是说是定义通知的自定义类。自定义的AOP类Aspect连接点方法调用&#xff0c;异常抛出可以增强的点JoinPoint &#xff1a;也就是**被增强的方法的总称&#xff0c;可以获取具体方法的信息&#xff…

初识Sringboot3+vue3环境准备

环境准备 后端环境准备 下载JDK17https://www.oracle.com/java/technologies/downloads/#jdk17-windows 安装就下一步下一步,选择安装路径 配置环境 环境 JDK17、IDEA2021、maven3.5、vscode 后端 基础&#xff1a;javaSE&#xff0c;javaWeb、JDBC、SMM框架&#xff08;Spr…

Unity JSON编码解码之LitJson 深度剖析

把LitJson的代码库放入到项目中&#xff0c;如图所示:JSON在游戏开发中是一种序列化/反序列化常用的技术&#xff0c;把游戏相关的数据,如地图组成,通过JSON编码&#xff0c;序列化成JSON文本&#xff0c;传输或存储, 要使用的时候再通过JSON技术把文本解析成数据对象&#xff…

竞赛保研 基于卷积神经网络的乳腺癌分类 深度学习 医学图像

文章目录 1 前言2 前言3 数据集3.1 良性样本3.2 病变样本 4 开发环境5 代码实现5.1 实现流程5.2 部分代码实现5.2.1 导入库5.2.2 图像加载5.2.3 标记5.2.4 分组5.2.5 构建模型训练 6 分析指标6.1 精度&#xff0c;召回率和F1度量6.2 混淆矩阵 7 结果和结论8 最后 1 前言 &…

SSM驾校预约管理系统----计算机毕业设计

项目介绍 本项目分为管理员、教练、学员三种角色&#xff0c; 管理员角色包含以下功能&#xff1a; 学员管理、教练管理、车辆管理、关系管理、车辆维修管理、个人中心等功能。 教练角色包含以下功能&#xff1a; 我的课程、我的学员、车辆中心、个人中心等功能。 学员角色包…

跟着LearnOpenGL学习12--光照贴图

文章目录 一、前言二、漫反射贴图三、镜面光贴图3.1、采样镜面光贴图 一、前言 在跟着LearnOpenGL学习11–材质中&#xff0c;我们讨论了让每个物体都拥有自己独特的材质从而对光照做出不同的反应的方法。这样子能够很容易在一个光照的场景中给每个物体一个独特的外观&#xf…

【开源】基于JAVA语言的创意工坊双创管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 管理员端2.2 Web 端2.3 移动端 三、系统展示四、核心代码4.1 查询项目4.2 移动端新增团队4.3 查询讲座4.4 讲座收藏4.5 小程序登录 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的创意工坊双创管理…

TwIST算法MALTLAB主程序详解

TwIST算法MALTLAB主程序详解 关于TwIST算法的具体原理可以参考&#xff1a; 链接: https://ieeexplore.ieee.org/abstract/document/4358846 链接: https://blog.csdn.net/jbb0523/article/details/52193209 该算法的MATLAB源代码&#xff1a; 链接: http://www.lx.it.pt/~bi…

wireshark access/trunk/hybrid报文分析

1&#xff0c;access接口 发送带vlan的报文 wireshark交换机配置 [Huawei-GigabitEthernet0/0/1] [Huawei-GigabitEthernet0/0/1]port link-type access [Huawei-GigabitEthernet0/0/1]port default vlan 100 [Huawei-GigabitEthernet0/0/2]port link-type access [Huawei-Gig…

【HarmonyOS】鸿蒙开发简介与项目基础配置演示

从今天开始&#xff0c;博主将开设一门新的专栏用来讲解市面上比较热门的技术 “鸿蒙开发”&#xff0c;对于刚接触这项技术的小伙伴在学习鸿蒙开发之前&#xff0c;有必要先了解一下鸿蒙&#xff0c;从你的角度来讲&#xff0c;你认为什么是鸿蒙呢&#xff1f;它出现的意义又是…

Elasticsearch:升级索引以使用 ELSER 最新的模型

在此 notebook 中&#xff0c;我们将看到有关如何使用 Reindex API 将索引升级到 ELSER 模型 .elser_model_2 的示例。 注意&#xff1a;或者&#xff0c;你也可以通过 update_by_query 来更新索引以使用 ELSER。 在本笔记本中&#xff0c;我们将看到使用 Reindex API 的示例。…

MR实战:实现数据去重

文章目录 一、实战概述二、提出任务三、完成任务&#xff08;一&#xff09;准备数据文件1、在虚拟机上创建文本文件2、上传文件到HDFS指定目录 &#xff08;二&#xff09;实现步骤1、Map阶段实现&#xff08;1&#xff09;创建Maven项目&#xff08;2&#xff09;添加相关依赖…

命令模式-实例使用

未使用命令模式的UML 使用命令模式后的UML public abstract class Command {public abstract void execute(); }public class Invoker {private Command command;/*** 为功能键注入命令* param command*/public void setCommand(Command command) {this.command command;}/***…