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

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...