LeetCode 79. 单词搜索

news/2024/3/29 9:00:26/文章来源:https://blog.csdn.net/qq_41046821/article/details/129263124

LeetCode 79. 单词搜索

难度:middle\color{orange}{middle}middle


题目描述

给定一个 mxnm x nmxn 二维字符网格 boardboardboard 和一个字符串单词 wordwordword 。如果 wordwordword 存在于网格中,返回 truetruetrue ;否则,返回 falsefalsefalse

单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 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.lengthm == board.lengthm==board.length
  • n=board[i].lengthn = board[i].lengthn=board[i].length
  • 1<=m,n<=61 <= m, n <= 61<=m,n<=6
  • 1<=word.length<=151 <= word.length <= 151<=word.length<=15
  • boardboardboardwordwordword 仅由大小写英文字母组成

进阶: 你可以使用搜索剪枝的技术来优化解决方案,使其在 boardboardboard 更大的情况下可以更快解决问题?


算法

(递归)

在深度优先搜索中,最重要的就是考虑好搜索顺序。

我们先枚举单词的起点,然后依次枚举单词的每个字母。
过程中需要将已经使用过的字母改成一个特殊字母,以避免重复使用字符。

复杂度分析

  • 时间复杂度O(n23k)O(n^2 3^k)O(n23k),单词起点一共有 n2n^2n2 个,单词的每个字母一共有上下左右四个方向可以选择,但由于不能走回头路,所以除了单词首字母外,仅有三种选择。所以总时间复杂度是 O(n23k)O(n^2 3^k)O(n23k)

  • 空间复杂度 : O(n)O(n)O(n)

C++ 代码

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {for (int i = 0; i < board.size(); i ++) {for (int j = 0; j < board[0].size(); j ++) {if (dfs(board, word, 0, i, j)) return true;}}return false;}int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};bool dfs(vector<vector<char>>& board, string& word, int u, int x, int y) {if (board[x][y] != word[u]) return false;if (u == word.size() - 1) return true;char t = board[x][y];board[x][y] = '.';for (int i = 0; i < 4; i ++) {int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '.')continue;if (dfs(board, word, u + 1, a, b)) return true;}board[x][y] = t;return false;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_75562.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Leetcode19. 删除链表的倒数第n个结点

一、题目描述&#xff1a; 给你一个链表&#xff0c;删除链表的倒数第 n 个结点&#xff0c;并且返回链表的头结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], n 2输出&#xff1a;[1,2,3,5] 示例 2&#xff1a; 输入&#xff1a;head [1], n 1输出&#x…

JSP的分页

分页在读取数据库里的数据需要用&#xff0c;在以后数据库肯定还会有很多数据&#xff0c;一个页面装不下&#xff0c;所以需要分页功能。数据库查询的分页语句是“SELECT * FROM emp LIMIT 0, 5;”这里0是指起始行&#xff0c;5是查询5行&#xff0c;第二页起始行就是5&#x…

通过python技术获取甲流分布数据

近期&#xff0c;多地学校出现因甲流导致的班级停课&#xff0c;儿科甲流患者就诊量呈数倍增长。此轮甲流为何如此严重&#xff1f;感染甲流之后会出现哪些症状&#xff1f; 经过专家的介绍甲流之所以这么严重有这些原因导致的。一、疫情完全放开后很多孩子不戴口罩了&#x…

Odoo | Webserivce | 5分钟学会【JSONRPC】接口开发 - 换USERID(进阶)

文章目录JSONRPC - 换取USERID简述换取USERID1. 代码示例2. 换取结果JSONRPC - 换取USERID 简述 从Odoo JSONRPC 接口入门篇&#xff0c;可以发现我们直接传入了USERID&#xff0c;这只是为了方便快速测试。 其实按照常规流程&#xff0c;应该通过【用户名USERNAME】和【用户…

【办公类-19-02】Python批量制作word文本框的名字小标签,用A4word打印(植物角、家长会、值日生)

背景需求&#xff1a; 2月28日去小班带班&#xff0c;看到班主任制作了一些小手印花束作为家长会的家长座位提示&#xff0c;上面贴着“”圆形白色的幼儿名字贴”。 我立刻想起了制作的过程——在word中插入文本框&#xff0c;然后复制无数个文本框&#xff0c;摆好位置&#…

MyBatis学习笔记(八) —— 字段名和属性不一致的情况下,如何处理映射关系

EmpMapper.java /** * 根据id查询员工信息 * param empId * return */ Emp getEmpByEmpId(Param("empId") Integer empId);EmpMapper.xml <?xml version"1.0" encoding"UTF-8" ?> <!DOCTYPE mapper PUBLIC "-//mybatis.org//D…

day22_IO

今日内容 上课同步视频:CuteN饕餮的个人空间_哔哩哔哩_bilibili 同步笔记沐沐霸的博客_CSDN博客-Java2301 零、 复习昨日 一、作业 二、缓冲流 三、字符流 四、缓冲字符流 五、匿名内部类 零、 复习昨日 File: 通过路径代表一个文件或目录 方法: 创建型,查找类,判断类,其他 IO …

如何创建出实用的员工手册?

员工手册主要是企业内部的人事制度管理规范&#xff0c;包含企业规章制度和企业文化&#xff0c;同时还起到了展示企业形象、传播企业文化的作用。它既覆盖了企业人力资源管理的各个方面规章制度的主要内容&#xff0c;又因适应企业独特个性的经营发展需要而弥补了规章制度制定…

VIF_Benchmark: All infrare and visible image fusion method in one framework

VIF_Benchmark Github 地址: https://github.com/Linfeng-Tang/VIF_Benchmark 完整Project下载地址&#xff1a;https://download.csdn.net/download/fovever_/87514164 我们把所有主流的基于深度学习的红外和可见光图像融合方法都集成在了这个框架中。 这些方法包括&#xff1…

数据结构六大排序

1.插入排序 1.插入排序 思路&#xff1a; 从第一个元素开始认为是有序的&#xff0c;去一个元素tem从有序序列从后往前扫描&#xff0c;如果该元素大于tem&#xff0c;将该元素一刀下一位&#xff0c;循环步骤3知道找到有序序列中小于等于的元素将tem插入到该元素后&#xff0…

如何防止DNS污染?

对于DNS污染&#xff0c;一般除了使用代理服务器和VPN之类的软件之外&#xff0c;并没有什么其它办法。但是利用我们对DNS污染的了解&#xff0c;还是可以做到不用代理服务器和VPN之类的软件就能解决DNS污染的问题&#xff0c;从而在不使用代理服务器或VPN的情况下访问原本访问…

设计模式系列 - 代理模式及动态代理详解

定义 为其他对象提供一种代理以控制对这个对象的访问。在某些情况下&#xff0c;一个对象不适合或者不能直接引用另一个对象&#xff0c;而代理对象可以在客户端和目标对象之间起到中介的作用。 结构 抽象角色&#xff1a;通过接口或抽象类声明真实角色实现的业务方法。 代…

C++ STL:容器 Container

文章目录1、序列容器1.1、容器共性1.2、vectorvector 结构* vector 扩容原理* vector 迭代器失效1.3、dequedeque 结构deque 迭代器deque 模拟连续空间1.4、listlist 特殊操作list 结构list 迭代器2、关联式容器2.1、容器共性2.2、容器特性3、无序关联式容器3.1、容器共性3.2、…

电子科技大学 高级计算机系统结构 考试回忆

首先题量不算小&#xff0c;因此没有太多时间把题都记出来&#xff0c;但是叙述一下题的类型希望能帮到以后选了这门课大家&#xff0c;在网上确实没有搜到这门课有关考试的任何资料&#xff0c;所以我也没啥参考全凭记忆和老师的PPT结合。复习的时候老师给了大纲&#xff0c;就…

【k8s】Kubernetes的学习(1.k8s概念和架构)

目录 1.首先要知道&#xff0c;Kubernetes为什么简称为k8s? 2.Kubernetes概述 2.1 kubernetes基本介绍 2.2 kubernetes的特性 2.3 kubernetes集群架构组件 2.3.1 Master (主控节点) 2.3.2 node (工作节点) 2.4 k8s核心概念 2.4.1 Pod 2.4.2 controller 2.4.3 Se…

Python自动发周报给老板,到点赶紧跑

嗨害大家好鸭&#xff01;我是小熊猫~ 作为一个社畜人 …勤勤恳恳的打工人&#xff01;&#xff01;&#xff01; 几乎每周都要写周报 没办法只能用点小技术 用python写个小工具 让它来给老板发周报哈哈哈 更多python摸鱼小技巧、基础知识:点击此处跳转文末名片获取 目标细…

收下这份十万商家称赞的开店攻略,带你发家致富!

理想与现实之间的距离&#xff0c;大概就是开店吧&#xff01;总觉得自己投点钱&#xff0c;一两年回本&#xff0c;后面每月轻松赚几万、几十万&#xff1b;结果却发现房租太贵、人工太贵、自己什么都不懂&#xff0c;然后随波逐流的没有特色。其实&#xff0c;细心的朋友会发…

【VUE】二 vue指令

目录 一、插值表达式 二、v-bind指令(对标签中的属性进行操作) 三、v-model指令&#xff08;input、select、textarea等。【双向绑定】&#xff09; 四、v-for循环指令 五、v-on(事件指令) 六、v-if条件判断 七、v-show&#xff08;条件显示或隐藏&#xff09; 八、案例…

王道计算机网络课代表 - 考研计算机 第五章 传输层 究极精华总结笔记

本篇博客是考研期间学习王道课程 传送门 的笔记&#xff0c;以及一整年里对 计算机网络 知识点的理解的总结。希望对新一届的计算机考研人提供帮助&#xff01;&#xff01;&#xff01; 关于对 “传输层” 章节知识点总结的十分全面&#xff0c;涵括了《计算机网络》课程里的全…

MySQL 学习笔记(借鉴黑马程序员MySQL)

MySQL视频课链接 MySQL概述 数据库相关概念 数据库是存储数据的仓库&#xff0c;数据是有组织的进行存储&#xff08;DataBase&#xff09; 数据库管理系统是操纵和管理数据库的大型软件&#xff08;DataBase Management System&#xff09; SQL是操作关系型数据库的编程语…