当前位置: 首页 > 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] -…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

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

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

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...

Linux-进程间的通信

1、IPC&#xff1a; Inter Process Communication&#xff08;进程间通信&#xff09;&#xff1a; 由于每个进程在操作系统中有独立的地址空间&#xff0c;它们不能像线程那样直接访问彼此的内存&#xff0c;所以必须通过某种方式进行通信。 常见的 IPC 方式包括&#…...

FOPLP vs CoWoS

以下是 FOPLP&#xff08;Fan-out panel-level packaging 扇出型面板级封装&#xff09;与 CoWoS&#xff08;Chip on Wafer on Substrate&#xff09;两种先进封装技术的详细对比分析&#xff0c;涵盖技术原理、性能、成本、应用场景及市场趋势等维度&#xff1a; 一、技术原…...