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

力扣每日一题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 更大的情况下可以更快解决问题?

通过次数

462.9K

提交次数

997.8K

通过率

46.4%

思路和题解:

回溯和剪枝,设置一个函数check(i,j,k)判断从网格的下标[i][j]位置出发,能不能搜索到单词word[k]...word[wordSize-1](即word中下标k开始的后缀字符串)。判断所有的check(i,j,0),只要有一个为真即为真,否则为假。

对于check函数,如果board[i][j]!=word[k],return false;如果board[i][j]!=word[k]&&k==wordSize-1,return true;否则就判断相邻的四个位置能不能搜到word[k+1]...word[wordSize-1]。

要注意的是,check函数中包含了多次递归调用,如果是c++的话,参数写成传引用,这样比值传递运行速度快,能过。值传递的话我试过过不了。

i代码:

class Solution {
public://往右,左,下,上四个方向走时行下标的变化和列下标的变化int directions[4][2]={{0,1},{0,-1},{1,0},{-1,0}};bool check(vector<vector<char>> &board,int m,int n,vector<vector<int>> &visited,int i,int j,string word,int wordSize,int k){if(board[i][j]!=word[k])return false;else if(k==wordSize-1)return true;visited[i][j]=1;for(int direc=0;direc<4;direc++){//依次往四个方向走int newi=i+directions[direc][0],newj=j+directions[direc][1];if(newi>=0&&newi<m&&newj>=0&&newj<n&&visited[newi][newj]==0){bool flag=check(board,m,n,visited,newi,newj,word,wordSize,k+1);if(flag){return true;}}}visited[i][j]=0;return false;}bool exist(vector<vector<char>>& board, string word) {int m=board.size();int n=board[0].size();vector<vector<int>> visited(m,vector<int>(n,0));int wordSize=word.size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){bool flag=check(board,m,n,visited,i,j,word,wordSize,0);if(flag)return true;}}return false;}
};

相关文章:

力扣每日一题79:单词搜索

题目描述&#xff1a; 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 单词必须按照字母顺序&#xff0c;通过相邻的单元格内的字母构成&#xff0c;其中“相邻”单元格…...

ChatGPT如何应对用户提出的道德伦理困境?

ChatGPT在应对用户提出的道德伦理困境时&#xff0c;需要考虑众多复杂的因素。道德伦理问题涉及到价值观、原则、社会和文化背景&#xff0c;以及众多伦理理论。ChatGPT的设计和应用需要权衡各种考虑因素&#xff0c;以确保它不仅提供有用的信息&#xff0c;而且遵循伦理标准。…...

SpringBoot运行流程源码分析------阶段三(Spring Boot外化配置源码解析)

Spring Boot外化配置源码解析 外化配置简介 Spring Boot设计了非常特殊的加载指定属性文件&#xff08;PropertySouce&#xff09;的顺序&#xff0c;允许属性值合理的覆盖&#xff0c;属性值会以下面的优先级进行配置。home目录下的Devtool全局设置属性&#xff08;~/.sprin…...

环形链表-力扣

一、题目描述 题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 二、题解 解题思路&#xff1a; 快慢指针&#xff0c;即慢指针一次走一步&#xff0c;快指针一次走两步&#xff0c;两个指针从链表起始位置开始运行&#xff0c;…...

人生岁月年华

人生很长吗&#xff1f;不知道。只知道高中坐在教室里&#xff0c;闹哄哄的很难受。也记得上班时无聊敲着代码也很难受。 可是人生也不长。你没有太多时间去试错&#xff0c;你没有无限的时间精力去追寻你认为的高大上。 人生是何体验呢&#xff1f;人生的感觉很多吧。大多数…...

电脑QQ如何录制视频文件?

听说QQ可以录制视频&#xff0c;还很方便&#xff0c;请问该如何录制呢&#xff1f;是需要先打开QQ才可以录制吗&#xff1f;还是可以直接使用快捷键进行录制呢&#xff1f;录制的质量又如何呢&#xff1f; 不要着急&#xff0c;既然都打开这篇文章看了&#xff0c;那小编今天…...

python:多波段遥感影像分离成单波段影像

作者:CSDN @ _养乐多_ 在遥感图像处理中,我们经常需要将多波段遥感影像拆分成多个单波段图像,以便进行各种分析和后续处理。本篇博客将介绍一个用Python编写的程序,该程序可以读取多波段遥感影像,将其拆分为单波段图像,并保存为单独的文件。本程序使用GDAL库来处理遥感影…...

天堂2游戏出错如何解决

运行游戏时出现以下提示&#xff1a;“the game may not be consistant because AGP is deactivated please activate AGP for consistancy” 这个问题的原因可能是由于您的显示卡的驱动或者主板的显示芯片组的驱动不是新开。或您虽然已经更新了您的显示卡的驱动程序&#xff0…...

『力扣刷题本』:合并两个有序链表(递归解法)

一、题目 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4]示例 2&#xff1a; 输入&#xff1a;l1 [], l2 [] 输出&#x…...

C++设计模式_12_Singleton 单件模式

在之前的博文C57个入门知识点_44&#xff1a;单例的实现与理解中&#xff0c;已经详细介绍了单例模式&#xff0c;并且根据其中内容&#xff0c;单例模式已经可以在日常编码中被使用&#xff0c;本文将会再做梳理。 Singleton 单件模式可以说是最简单的设计模式&#xff0c;但由…...

67 内网安全-域横向smbwmi明文或hash传递

#知识点1: windows2012以上版本默认关闭wdigest&#xff0c;攻击者无法从内存中获取明文密码windows2012以下版本如安装KB2871997补丁&#xff0c;同样也会导致无法获取明文密码针对以上情况&#xff0c;我们提供了4种方式解决此类问题 1.利用哈希hash传递(pth&#xff0c;ptk等…...

面向对象(类/继承/封装/多态)详解

简介: 面向对象编程&#xff08;Object-Oriented Programming&#xff0c;OOP&#xff09;是一种广泛应用于软件开发的编程范式。它基于一系列核心概念&#xff0c;包括类、继承、封装和多态。在这篇详细的解释中&#xff0c;我们将探讨这些概念&#xff0c;并说明它们如何在P…...

【Python机器学习】零基础掌握GradientBoostingRegressor集成学习

如何精准预测房价? 当人们提到房价预测时,很多人可能会想到房地产经纪人或专业的评估师。但是,有没有一种更科学、更精确的方法来预测房价呢?答案是有的,这就要用到机器学习中的一种算法——梯度提升回归(Gradient Boosting Regressor)。 假设现在有一组房屋数据,包括…...

【tio-websocket】12、应用层包—Packet

Packet 介绍 Packet 是用于表述业务数据结构的,我们通过继承 Packet 来实现自己的业务数据结构,对于各位而言,把 Packet 看作是一个普通的 VO 对象即可。 public class Packet implements java.io.Serializable, Cloneable {private static Logger log = LoggerFac…...

OpenCV官方教程中文版 —— 模板匹配

OpenCV官方教程中文版 —— 模板匹配 前言一、原理二、OpenCV 中的模板匹配三、多对象的模板匹配 前言 在本节我们要学习&#xff1a; 使用模板匹配在一幅图像中查找目标 函数&#xff1a;cv2.matchTemplate()&#xff0c;cv2.minMaxLoc() 一、原理 模板匹配是用来在一副大…...

如何为3D模型设置自发光材质?

1、自发光贴图的原理 自发光贴图是一种纹理贴图&#xff0c;用于模拟物体自发光的效果。其原理基于光的发射和反射过程。 在真实世界中&#xff0c;物体自发光通常是由于其本身具有能够产生光的属性&#xff0c;如荧光物质、发光材料或光源本身。为了在计算机图形中模拟这种效…...

UI组件库基础

UI组件库 全局组件* 全局注册组件 & 并且使用了require.context 模块化编程 & webpack打包 const install(Vue)>{const contextrequire.context(.,true,/\.vue$/)context.keys().forEach(fileName>{const modulecontext(fileName)Vue.component(module.default.n…...

数据结构与算法之矩阵: Leetcode 48. 旋转矩阵 (Typescript版)

旋转图像 https://leetcode.cn/problems/rotate-image/ 描述 给定一个 n n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像&#xff0c;这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1 输入&…...

大厂面试题-JVM中的三色标记法是什么?

目录 问题分析 问题答案 问题分析 三色标记法是Java虚拟机(JVM)中垃圾回收算法的一种&#xff0c;主要用来标记内存中存活和需要回收的对象。 它的好处是&#xff0c;可以让JVM不发生或仅短时间发生STW(Stop The World)&#xff0c;从而达到清除JVM内存垃圾的目的&#xff…...

Leetcode—121.买卖股票的最佳时机【简单】

2023每日刷题&#xff08;十一&#xff09; Leetcode—17.电话号码的字母组合 枚举法题解 参考自灵茶山艾府 枚举法实现代码 int maxProfit(int* prices, int pricesSize){int i;int max 0;int minPrice prices[0];for(i 1; i < pricesSize; i) {int tmp prices[i] -…...

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

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

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...