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

LeetCode79. Word Search——回溯

文章目录

    • 一、题目
    • 二、题解

一、题目

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
Output: true
Example 2:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
Output: true
Example 3:

Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB”
Output: false

Constraints:

m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board and word consists of only lowercase and uppercase English letters.

Follow up: Could you use search pruning to make your solution faster with a larger board?

二、题解

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {int m = board.size(),n = board[0].size();for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(f(board,i,j,word,0)) return true;}}return false;}//从i,j位置出发来到word[k]位置,后续字符是否能走出来bool f(vector<vector<char>>& board,int i,int j,string word,int k){if(k == word.size()) return true;if(i < 0 || i == board.size() || j < 0 || j == board[0].size() || board[i][j] != word[k]) return false;char t = board[i][j];//为了不重复走board[i][j] = '0';bool res = f(board,i-1,j,word,k+1) || f(board,i+1,j,word,k+1) || f(board,i,j-1,word,k+1) || f(board,i,j+1,word,k+1);board[i][j] = t;return res;}
};

相关文章:

LeetCode79. Word Search——回溯

文章目录 一、题目二、题解 一、题目 Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertic…...

Linux命令-blkid命令(查看块设备的文件系统类型、LABEL、UUID等信息)

说明 在Linux下可以使用 blkid命令 对查询设备上所采用文件系统类型进行查询。blkid主要用来对系统的块设备&#xff08;包括交换分区&#xff09;所使用的文件系统类型、LABEL、UUID等信息进行查询。要使用这个命令必须安装e2fsprogs软件包。 语法 blkid -L | -U blkid [-c…...

服务治理中间件-Eureka

目录 简介 搭建Eureka服务 注册服务到Eureka 简介 Eureka是Spring团队开发的服务治理中间件&#xff0c;可以轻松在项目中&#xff0c;实现服务的注册与发现&#xff0c;相比于阿里巴巴的Nacos、Apache基金会的Zookeeper&#xff0c;更加契合Spring项目&#xff0c;缺点就是…...

Javaweb之SpringBootWeb案例之异常处理功能的详细解析

3. 异常处理 3.1 当前问题 登录功能和登录校验功能我们都实现了&#xff0c;下面我们学习下今天最后一块技术点&#xff1a;异常处理。首先我们先来看一下系统出现异常之后会发生什么现象&#xff0c;再来介绍异常处理的方案。 我们打开浏览器&#xff0c;访问系统中的新增部…...

苹果Mac键盘如何将 F1 到 F12 取消按Fn

苹果电脑安装了Win10操作系统之后&#xff0c;F1到F12用不了怎么办的解决方法。本文将介绍一些解决方法&#xff0c;帮助您解决无法使用F1到F12功能键的问题。 使用 Mac系统的人都知道&#xff0c;Mac系统默认是没有开启 F1-F12 的使用的&#xff0c;平时我们使用的系统都可以使…...

linux下ipconfig命令报:command not found 解决方法

参考博文&#xff1a; linux下ipconfig命令报:command not found 解决方法 CentOS7更新yum报Could not resolve host:mirrorlist.centos.org; Unknown error解决办法...

Android导入其它项目慢,Gradel下载失败,另辟蹊径:使用离线gradle加载,附镜像方式

最近在开发中需要测试以前写的小项目。结果忘了换本地的gradle&#xff0c;提示下载失败。换了现在用的gradle&#xff0c;项目能跑了。虽然网上有很多很多教程了&#xff0c;但对我的情况也不是都适用。所以自己记录一下。本人水平有限&#xff0c;有不对的地方请帮我指正&…...

神经语言程式(NLP)项目的15 个开源训练数据集

一个聊天机器人需要大量的训练数据,以便在无需人工干预的情况下快速解决用户的询问。然而,聊天机器人开发的主要瓶颈是获取现实的、面向任务的对话数据来训练这些基于机器学习的系统。 我们整理了训练聊天机器人所需的对话数据集,包括问答数据、客户支持数据、对话数据和多…...

H5 红色文字抖动网址发布页/引导页源码

H5 红色文字抖动网址发布页/引导页源码 源码介绍&#xff1a;一款红色文字抖动网页源码&#xff0c;可用于引导页或网址发布页。 下载地址&#xff1a; https://www.changyouzuhao.cn/10470.html...

MacOS - 菜单栏上显示『音量』

教程步骤 点击打开系统偏好『设置』&#xff0c;并找到『控制中心』 在『控制中心模块』找到『声音』&#xff0c;选择『始终在菜单栏显示』...

深入理解常见的设计模式

目录 引言 1. 单例模式&#xff08;Singleton Pattern&#xff09; 应用场景&#xff1a; 示例代码&#xff1a; . 工厂模式&#xff08;Factory Pattern&#xff09; 应用场景&#xff1a; 示例代码&#xff1a; 3. 观察者模式&#xff08;Observer Pattern&#xff09…...

服务器解析漏洞及任意文件下载

1.服务器文件解析漏洞 文件解析漏洞,是指Web容器&#xff08;Apache、nginx、iis等&#xff09;在解析文件时出现了漏洞,以其他格式执行出脚本格式的效果。从而,黑客可以利用该漏洞实现非法文件的解析。 &#xff08;1) Apache linux系统中的apache的php配置文件在/etc/apac…...

ES6扩展运算符——三个点(...)用法详解

目录 1 含义 2 替代数组的 apply 方法 3 扩展运算符的应用 &#xff08; 1 &#xff09;合并数组 &#xff08; 2 &#xff09;与解构赋值结合 &#xff08; 3 &#xff09;函数的返回值 &#xff08; 4 &#xff09;字符串 &#xff08; 5 &#xff09;实现了 Iter…...

限制资源使用

限制资源使用 您需要显示对服务器资源的访问来保护Web应用程序和应用程序数据不受未授权用户的访问。在Java EE Web应用程序中,您可以通过在应用服务器中创建用户和用户组来保护资源免受未经授权的访问。您可以为应用程序定义角色并在部署过程中将角色分配给用户。 1. 创建授权…...

结合Next项目实际认识webpack.splitChunks

本文的目的在于简单的介绍webpack的优化功能配置&#xff1a;splitChunks。 webpack5出于“开箱即用”的目的&#xff0c;将大部分曾经要使用插件的功能集成到了config配置中&#xff0c;因此用户只需要了解如何配置&#xff0c;即可达到优化目的&#xff0c;其中最常使用接触的…...

【Tauri】(2):使用Tauri应用开发,使用开源的Chatgpt-web应用做前端,使用rust 的candle做后端,本地运行小模型桌面应用

视频演示地址 https://www.bilibili.com/video/BV17j421X7Zc/ 【Tauri】&#xff08;2&#xff09;&#xff1a;使用Tauri应用开发&#xff0c;使用开源的Chatgpt-web应用做前端&#xff0c;使用rust 的candle做后端&#xff0c;本地运行小模型桌面应用 1&#xff0c;做一个免…...

C#where T :通用的泛型约束(generic constraint)语法

在C#中&#xff0c;where T :是一种通用的泛型约束&#xff08;generic constraint&#xff09;语法&#xff0c;用于限制泛型类型参数T的特定条件。通过使用泛型约束&#xff0c;我们可以对泛型类型参数进行更具体的限制&#xff0c;以确保在使用泛型时满足特定的要求。 wher…...

vue使用Mars3d弹框嵌套video视频/实时视频(m3u8)使用hls.js

下载hls.js http://mars3d.cn/lib/video/hls/hls.js下载 1.首先绘制地图我使用的天地图 async infoMars3d() {const that this;var mapOptions {scene: {center: {lat: 30.435192,lng: 103.936535,alt: 200000,heading: 359,pitch: -79},highDynamicRange: false},// 方式1&a…...

Python爬虫之Ajax数据爬取基本原理

前言 有时候我们在用 requests 抓取页面的时候&#xff0c;得到的结果可能和在浏览器中看到的不一样&#xff1a;在浏览器中可以看到正常显示的页面数据&#xff0c;但是使用 requests 得到的结果并没有。这是因为 requests 获取的都是原始的 HTML 文档&#xff0c;而浏览器中…...

osg操控器和键盘切换操控器学习

osg提供了很多操控器,在src\osgGA目录下,cpp文件名含有Manipulator的都是操控器,每个这样的cpp表示一种类型的操控器。 名字带 Manipulator 的类都是操控器; 其中KeySwitchMatrixManipulator.cpp文件实现了键盘切换操控器; 操控器是指:操控相机运动,从而实现场景视图…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

聊一聊接口测试的意义有哪些?

目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开&#xff0c;首…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测

uniapp 中配置 配置manifest 文档&#xff1a;manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号&#xff1a;4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...