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

刷题记录 HOT100回溯算法-6:79. 单词搜索

题目: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 仅由大小写英文字母组成

一、模式识别

1.棋盘格:回溯法

棋盘格问题,回溯法典型应用,用回溯算法

层间:word内顺序访问

层内:board遍历或上一个字母上下左右

无需找到所有结果,找到第一个结果后返回

2.搜索方式

1.word首字母在board中二维遍历

2.word内(层间)顺序访问,剩余字母分别搜索上一个字母的上下左右

3.访问过的字母不可以重复访问

二.代码实现

1.基础实现

class Solution:def get_candidate(self, board, visited, i, j):candidate = []if i - 1 >= 0 and not visited[i - 1][j]:candidate.append((board[i - 1][j], i - 1, j))if j - 1 >= 0 and not visited[i][j - 1]:candidate.append((board[i][j - 1], i, j - 1))if i + 1 < len(board) and not visited[i + 1][j]:candidate.append((board[i + 1][j], i + 1, j))if j + 1 < len(board[0]) and not visited[i][j + 1]:candidate.append((board[i][j + 1], i, j + 1))return candidatedef backtracking(self, board, word, visited, start_idx, i, j):if start_idx == len(word):return Trueif start_idx == 0:for i in range(len(board)):for j in range(len(board[i])):if board[i][j] == word[0]:visited[i][j] = Trueif self.backtracking(board, word, visited, 1, i, j):return Truevisited[i][j] = Falseelse:for ch, a, b in self.get_candidate(board, visited, i, j):if ch == word[start_idx]:visited[a][b] = Trueif self.backtracking(board, word, visited, start_idx + 1, a, b):return Truevisited[a][b] = Falsereturn Falsedef exist(self, board: List[List[str]], word: str) -> bool:visited = [[False] * len(board[0]) for _ in range(len(board))]return self.backtracking(board, word, visited, 0, -1, -1)

start_idx记录访问顺序

visited用于标记访问过的字母

首字母二维遍历board

剩余字母层间顺序访问,层内访问上一个字母在board中的上下左右

耗时:2000ms-4000ms

2.启发式搜索

class Solution:def get_candidate(self, board, i, j):candidate = []if i - 1 >= 0 and board[i - 1][j]:candidate.append((board[i - 1][j], i - 1, j))if j - 1 >= 0 and board[i][j - 1]:candidate.append((board[i][j - 1], i, j - 1))if i + 1 < len(board) and board[i + 1][j]:candidate.append((board[i + 1][j], i + 1, j))if j + 1 < len(board[0]) and board[i][j + 1]:candidate.append((board[i][j + 1], i, j + 1))return candidatedef backtracking(self, board, word, start_idx, i, j):if start_idx == len(word):return Trueif start_idx == 0:for i in range(len(board)):for j in range(len(board[i])):if board[i][j] == word[0]:board[i][j] = Falseif self.backtracking(board, word, 1, i, j):return Trueboard[i][j] = word[0]else:for ch, a, b in self.get_candidate(board, i, j):if ch == word[start_idx]:board[a][b] = Falseif self.backtracking(board, word, start_idx + 1, a, b):return Trueboard[a][b] = word[start_idx]return Falsedef exist(self, board: List[List[str]], word: str) -> bool:# visited = [[False] * len(board[0]) for _ in range(len(board))]cnt=Counter(c for row in board for c in row)if not cnt>=Counter(word):return Falseif cnt[word[-1]]<cnt[word[0]]:word=word[::-1]return self.backtracking(board, word, 0, -1, -1)

在提交排行榜中看到的启发式搜索

思路:主要搜索开销都在第一步的board的遍历,于是从第一步开刀

实现逻辑:如果尾端字母在board出现频率低于首端则word反序

计算开销直接降到0ms-3ms

相关文章:

刷题记录 HOT100回溯算法-6:79. 单词搜索

题目&#xff1a;79. 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 单词必须按照字母顺序&#xff0c;通过相邻的单元格内的字母构成&#xff0c;其中“相邻…...

JavaScript系列(52)--编译优化技术详解

JavaScript编译优化技术详解 &#x1f680; 今天&#xff0c;让我们深入探讨JavaScript的编译优化技术。通过理解和应用这些技术&#xff0c;我们可以显著提升JavaScript代码的执行效率。 编译优化基础概念 &#x1f31f; &#x1f4a1; 小知识&#xff1a;JavaScript引擎通常…...

Ollama+DeepSeek本地大模型部署

1、Ollama 官网&#xff1a;https://ollama.com/ Ollama可以干什么&#xff1f; 可以快速在本地部署和管理各种大语言模型&#xff0c;操作命令和dokcer类似。 mac安装ollama&#xff1a; # 安装ollama brew install ollama# 启动ollama服务&#xff08;默认11434端口&#xf…...

在 WSL2 中重启 Ubuntu 实例

在 WSL2 中重启 Ubuntu 实例&#xff0c;可以按照以下步骤操作&#xff1a; 方法 1: 使用 wsl 命令 关闭 Ubuntu 实例: 打开 PowerShell 或命令提示符&#xff0c;运行以下命令&#xff1a; wsl --shutdown这会关闭所有 WSL2 实例。 重新启动 Ubuntu: 再次打开 Ubuntu&#x…...

【ts + java】古玩系统开发总结

src别名的配置 开发中文件和文件的关系会比较复杂&#xff0c;我们需要给src文件夹一个别名吧 vite.config.js import { defineConfig } from vite import vue from vitejs/plugin-vue import path from path// https://vitejs.dev/config/ export default defineConfig({pl…...

机器学习周报-文献阅读

文章目录 摘要Abstract 1 相关知识1.1 WDN建模1.2 掩码操作&#xff08;Masking Operation&#xff09; 2 论文内容2.1 WDN信息的数据处理2.2 使用所收集的数据构造模型2.2.1 Gated graph neural network2.2.2 Masking operation2.2.3 Training loss2.2.4 Evaluation metrics 2…...

LabVIEW微位移平台位移控制系统

本文介绍了基于LabVIEW的微位移平台位移控制系统的研究。通过设计一个闭环控制系统&#xff0c;针对微位移平台的通信驱动问题进行了解决&#xff0c;并提出了一种LabVIEW的应用方案&#xff0c;用于监控和控制微位移平台的位移&#xff0c;从而提高系统的精度和稳定性。 项目背…...

fpga系列 HDL:XILINX Vivado ILA FPGA 在线逻辑分析

ILA为内置逻辑分析仪&#xff0c;通过JTAG与FPGA连接&#xff0c;程序在真实硬件中运行&#xff0c;功能类似Quaruts的SignalTap II 。 ip创建ila 使用ila ip核 timescale 1ns / 1ps module HLSLED(input wire clk ,input wire rst_n ,output wire led);// reg led_o_i 1…...

刷题记录 贪心算法-2:455. 分发饼干

题目&#xff1a;455. 分发饼干 难度&#xff1a;简单 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&#xff0c;都有一个胃口值 g[i]&#xff0c;这是能让孩子们满足胃口的饼干的最小尺寸&a…...

Android --- CameraX讲解

预备知识 surface surfaceView SurfaceHolder surface 是什么&#xff1f; 一句话来说&#xff1a; surface是一块用于填充图像数据的内存。 surfaceView 是什么&#xff1f; 它是一个显示surface 的View。 在app中仍在 ViewHierachy 中&#xff0c;但在wms 中可以理解为…...

ElasticSearch view

基础知识类 elasticsearch和数据库之间区别&#xff1f; elasticsearch&#xff1a;面向文档&#xff0c;数据以文档的形式存储&#xff0c;即JSON格式的对象。更强调数据的搜索、索引和分析。 数据库&#xff1a;更侧重于事务处理、数据的严格结构化和完整性&#xff0c;适用于…...

list的使用,及部分功能的模拟实现(C++)

目录&#xff08;文章中"节点"和"结点"是同一个意思&#xff09; 1. list的介绍及使用 1.1 list的介绍 1.2 list的使用 1.2.1 list的构造 1.2.2 list iterator的使用 1.2.3 list capacity 1.2.4 list element access 1.2.5 list modifiers 1.2.6 list…...

联想Y7000+RTX4060+i7+Ubuntu22.04运行DeepSeek开源多模态大模型Janus-Pro-1B+本地部署

直接上手搓了&#xff1a; conda create -n myenv python3.10 -ygit clone https://github.com/deepseek-ai/Janus.gitcd Januspip install -e .pip install webencodings beautifulsoup4 tinycss2pip install -e .[gradio]pip install pexpect>4.3python demo/app_januspr…...

[Spring] Gateway详解

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏: &#x1f9ca; Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm1001.2014.3001.5482 &#x1f355; Collection与…...

音叉模态分析

目录 0 序言 1 自由状态下模态求解 1.1 添加模态项目 1.2 生成网格 1.3 设置最大模态阶数 1.4 求解 1.5 结果查看 1.6 结果分析 2 音叉能否释放频率440Hz的音调 3 预应力模态求解 3.1 静态结构分析 3.1.1 添加静态结构项目 3.1.2生成网格 3.1.3添加边界条件 3.1…...

BW AO/工作簿权限配置

场景&#xff1a; 按事业部配置工作簿权限&#xff1b; 1、创建用户 事务码&#xff1a;SU01&#xff0c;用户主数据的维护&#xff0c;可以创建、修改、删除、锁定、解锁、修改密码等 用户设置详情页 2、创建权限角色 用户的权限菜单是通过权限角色分配来实现的 2.1、自定…...

C++ 字母大小写转换两种方法统计数字字符的个数

目录 题目&#xff1a; 代码1&#xff1a; 代码2&#xff1a; 题目描述输入一行字符&#xff0c;统计出其中数字字符的个数。 代码如下&#xff1a; 判断⼀个字符是否是数字字符有⼀个函数是 isdigit ,可以直接使⽤。 代码如下&#xff1a; 题目&#xff1a; 大家都知道…...

如何使用 ChatBox AI 简化本地模型对话操作

部署模型请看上一篇帖子&#xff1a;本地部署DeepSeek教程&#xff08;Mac版本&#xff09;-CSDN博客 使用 ChatBox AI 简化本地模型对话操作&#xff1a; 打开 ChatBox AI 官网&#xff1a;Chatbox AI官网&#xff1a;办公学习的AI好助手&#xff0c;全平台AI客户端&#xf…...

前端面试笔试题目(一)

以下模拟了大厂前端面试流程&#xff0c;并给出了涵盖HTML、CSS、JavaScript等基础和进阶知识的前端笔试题目&#xff0c;以帮助你更好地准备面试。 面试流程模拟 1. 自我介绍&#xff08;5 - 10分钟&#xff09;&#xff1a;面试官会请你进行简单的自我介绍&#xff0c;包括…...

Docker Hello World

Docker Hello World 引言 Docker 是一个开源的应用容器引擎,可以让开发者打包他们的应用以及应用的依赖包到一个可移植的容器中,然后发布到任何流行的 Linux 机器上,也可以实现虚拟化。本文将带领您从零开始,学习如何使用 Docker 运行一个简单的 "Hello World"…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...