LeetCode79. Word Search——回溯

news/2024/2/21 2:59:58

文章目录

    • 一、题目
    • 二、题解

一、题目

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;}
};

https://www.xjx100.cn/news/3270986.html

相关文章

「计算机网络」物理层

物理层的基本概念 物理层的作用&#xff1a;尽可能屏蔽掉不同传输媒体和通信手段的差异物理层规程&#xff1a;用于物理层的协议主要任务&#xff1a;确定与传输媒体的接口有关的一些特性 机械特性电器特性功能特性过程特性 数据通信的基础知识 数据通信系统的模型 划分为…

IM聊天系统为什么需要做消息幂等?如何使用Redis以及Lua脚本做消息幂等【第12期】

0前言 消息收发模型 第一张图是一个时序图&#xff0c;第二张图是一个标清楚步骤的流程图&#xff0c;更加清晰。消息的插入环节主要在2步。save部分。主要也是对这个部分就行消息幂等的操作。 前情提要&#xff1a;使用Redis发布 token 以及lua脚本来共同完成消息的幂等 目…

使用深度学习进行“序列到序列”回归

目录 下载数据 准备训练数据 定义网络架构 训练网络 测试网络 此示例说明如何使用深度学习预测发动机的剩余使用寿命 (RUL)。 要训练深度神经网络以根据时间序列数据或序列数据预测数值,可以使用长短期记忆 (LSTM) 网络。 此示例使用 [1] 中所述的涡轮风扇发动机…

23种设计模式之抽象工厂模式

目录 什么是抽象工厂模式 基本结构 基本实现步骤 实现代码&#xff08;有注释&#xff09; 应用场景 简单工厂、工厂方法、抽象工厂的区别 什么是抽象工厂模式 抽象工厂模式也是一种创建型设计模式&#xff0c;提供了一系列相关或相互依赖对象的接口&#xff0c;而无需…

GO 的 Web 开发系列(五)—— 使用 Swagger 生成一份好看的接口文档

经过前面的文章&#xff0c;已经完成了 Web 系统基础功能的搭建&#xff0c;也实现了 API 接口、HTML 模板渲染等功能。接下来要做的就是使用 Swagger 工具&#xff0c;为这些 Api 接口生成一份好看的接口文档。 一、写注释 注释是 Swagger 的灵魂&#xff0c;Swagger 是通过…

SQLyog安装配置(注册码)连接MySQL

下载资源 博主给你打包好了安装包&#xff0c;在网盘里&#xff0c;只有几Mb&#xff0c;防止你下载到钓鱼软件 快说谢谢博主&#xff08;然后心甘情愿的点个赞~&#x1f60a;&#xff09; SQLyog.zip 安装流程 ①下载好压缩包后并解压 ②打开文件夹&#xff0c;双击安装包 ③…

使用R语言建立回归模型并分割训练集和测试集

通过简单的回归实例&#xff0c;可以说明数据分割为训练集和测试集的必要性。以下先建立示例数据: set.seed(123) #设置随机种子 x <- rnorm(100, 2, 1) # 生成100个正态分布的随机数&#xff0c;均值为2&#xff0c;标准差为1 y exp(x) rnorm(5, 0, 2) # 生成一个新的变…

Redis中缓存问题

缓存预热 Redis缓存预热是一项关键任务&#xff0c;可帮助提升应用程序的性能和响应速度。在高流量的应用程序中&#xff0c;Redis缓存预热可以加速数据查询和读取&#xff0c;从而改善用户体验。本文将介绍一种快速、稳定的Redis缓存预热方案&#xff0c;并提供相应代码实现。…