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

212. 单词搜索 II【力扣(LeetCode) 】

news 来源：原创 2025/7/17 11:26:23

文章目录

零、原题链接
一、题目描述
二、测试用例
三、解题思路
四、参考代码

零、原题链接

212. 单词搜索 II

一、题目描述

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，返回所有二维网格上的单词。

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

二、测试用例

示例 1：

在这里插入图片描述

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

示例 2：

在这里插入图片描述

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

提示：

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] 是一个小写英文字母
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] 由小写英文字母组成
words 中的所有字符串互不相同

三、解题思路

基本思路：
通过字典树来对深度搜索进行剪枝。
具体思路：
- 将 words 的字符构建成字典树；
- 深度搜索 board ：
  - 如果下标违法，则返回；
  - 如果该格子已经遍历过，则返回；
  - 如果字典树不存在该路径，则返回；【剪枝】
  - 如果字典树遍历到一个单词，则记录；
  - 将当前格子设置为 '#' ；【防止重复遍历】
  - 递归遍历邻居四个格子；
  - 恢复当前格子原本的内容；
- 遍历字典树，将记录的单词存放到 ans 中；
- 返回 ans 。

四、参考代码

时间复杂度： $\Omicron(m \cdot n \cdot 3^{l-1})$ 【构建字典树和遍历字典树的复杂度都没有深度遍历 board 高，而深度遍历 board ，每个格子都进行深度递归，有 $m\cdot n$ 个格子，深度递归最长路径为单词最长长度 $l$ ，递归的复杂度为 $4\cdot 3^{l-1}$ 】
空间复杂度： $\Omicron(mn+kl)$ 【存放 board + 存放字典树】

struct Node {Node* next[26] = {nullptr};string word;bool flag;Node() : word(""), flag(false) {}
};
class Solution {
public:vector<vector<char>> m_board;vector<pair<int, int>> pos = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int m, n;Node* root;vector<string> ans;void dfs(const int& i, const int& j, Node* p) {if (i < 0 || i >= m || j < 0 || j >= n) // 坐标不合法return;if (m_board[i][j] == '#') // 已经遍历过return;if (p->next[m_board[i][j] - 'a'] == nullptr)return;if (p->next[m_board[i][j] - 'a']->word.length() != 0) {p->next[m_board[i][j] - 'a']->flag = true;}char t = m_board[i][j];m_board[i][j] = '#';for (int x = 0; x < pos.size(); x++) {dfs(i + pos[x].first, j + pos[x].second, p->next[t - 'a']);}m_board[i][j] = t;}void setans(Node* p) {if (p->flag)ans.emplace_back(p->word);for (int i = 0; i < 26; i++) {if (p->next[i] == nullptr)continue;setans(p->next[i]);}}vector<string> findWords(vector<vector<char>>& board,vector<string>& words) {m_board = board;m = board.size();n = board[0].size();root = new Node();// 构建字典树for (int i = 0; i < words.size(); i++) {Node* p = root;for (int j = 0; j < words[i].size(); j++) {if (p->next[words[i][j] - 'a'] == nullptr) {p->next[words[i][j] - 'a'] = new Node();}p = p->next[words[i][j] - 'a'];}p->word = words[i];}// 确认是否存在for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {dfs(i, j, root);}}setans(root);return ans;}
};

212. 单词搜索 II【力扣(LeetCode) 】

文章目录零、原题链接一、题目描述二、测试用例三、解题思路四、参考代码零、原题链接 212. 单词搜索 II 一、题目描述给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词。单词必须按照字母…...

编程日记 2025/7/17 11:26:23

【软考-高级】【信息系统项目管理师】论文写作注意事项及2014年至2024年历年论文题目汇总

论文写作注意事项要求字数要求：2500字以内（2024年超过2500字，在线答题系统无法输入）时长要求：2小时（大多数人不够用）内容要求： 必须响应子标题，如子标题要求写如何优…...

编程日记 2025/7/16 14:43:00

MySQL数据库表的约束

目录 1.null属性 2.默认值约束（default） 3.comment 4.zerofill 5.主键（primary key） 6.自增长（auto_increment） 7.唯一键（unique） 编辑 8.外键约束是为了安全插入数据&a…...

编程日记 2025/7/17 11:06:16

硅基计划2.0 学习总结壹 Java初阶

一、初见Java （1）Java简介首先不得不承认Java是一门优秀的程序设计语言其系列的计算机软件和跨平台体系包括国内的生态链完善是C/C语言难以弥补的 （2）Java SE 全称Java Standard Edition，是Java体系的基础 &am…...

编程日记 2025/6/29 2:33:55

逆向破解：x64dbg

文章目录一、CPU窗口1、反汇编窗口2、寄存器窗口3、栈地址窗口4、十六进制数据窗口5、堆栈参数解析窗口二、常用快捷键三、字符串检索功能四、调试功能1、上一步一、CPU窗口 1、反汇编窗口 2、寄存器窗口寄存器窗口用于显示和解释当前线程环境下CPU寄存器的各种状态值和内…...

编程日记 2025/7/11 2:32:38

从MCU到SoC的开发思维转变

目录 1、硬件设计 2、软件开发 3、调试与测试 4、电源管理微控制器单元（MCU）和系统级芯片（SoC）是嵌入式开发中最常见的两种处理器类型。MCU以其简单、低功耗的特点，广泛应用于特定控制任务；而SoC凭借强…...

编程日记 2025/7/17 11:22:45

3DGS-to-PC：3DGS模型一键丝滑转点云 or Mesh 【Ubuntu 20.04】【2025最新版！！】

一、引言 3D高斯泼溅(3DGS)是一种新兴的三维场景表示方法，可以生成高质量的场景重建结果。然而，要查看这些重建场景，需要特殊的高斯渲染器。大多数3D处理软件并不兼容3D高斯分布模型，但它们通常都兼容点云文件。 3DGS-to-PC项目提…...

编程日记 2025/7/17 11:19:51

互联网大厂Java求职面试：优惠券服务架构设计与AI增强实践-3

互联网大厂Java求职面试：优惠券服务架构设计与AI增强实践-3 场景背景面试场景设定在一家大型互联网公司，面试官为拥有10年以上经验的技术总监，专注于高并发、高可用系统的架构设计。候选人郑薪苦是一名技术潜力十足的程序员，擅…...

编程日记 2025/7/4 14:40:11

ABP-Book Store Application中文讲解 - 前期准备 - Part 3:Acme.BookStore项目模块详解

ABP-Book Store Application中文讲解-汇总-CSDN博客本文通过对Acme.BookStore项目各模块的详解，让大家知道每个project用来干什么的，他们之间的引用关系是什么，同时知道怎样添加新的功能模块。 Acme.Bookstore 是主要 ABP Studio 模块的主…...

编程日记 2025/6/29 3:42:17

智慧城市综合运营管理系统Axure原型

这款Axure原型的设计理念紧紧围绕城市管理者的需求展开。它旨在打破传统城市管理中信息孤岛的局面，通过统一标准接入各类业务系统，实现城市运营管理信息资源的全面整合与共享。以城市管理者为中心，为其提供一个直观、便捷、高效的协同服务平台…...

编程日记 2025/6/29 1:39:10

Java中进阶并发编程

第一章、并发编程的挑战并发和并行：指多线程或多进程线程的本质：操作系统能够进行运算调度的最小单位，是进程（Process）中的实际工作单元进程的本质：操作系统进行资源分配和调度的基本单位&#xff0c…...

编程日记 2025/6/29 1:40:00

cursor 出现问题为客户解决问题

文档出自：https://www.kdocs.cn/l/cp5GpLHAWc0p...

编程日记 2025/6/29 1:37:00

【氮化镓】GaN在不同电子能量损失的SHI辐射下的损伤

该文的主要发现和结论如下： GaN的再结晶特性：GaN在离子撞击区域具有较高的再结晶倾向，这导致其形成永久损伤的阈值较高。在所有研究的电子能量损失 regime 下，GaN都表现出这种倾向，但在电子能量损失增加时，其效率会降低，尤其是在材料发生解离并形成N₂气泡时。能量损失…...

编程日记 2025/7/17 11:11:35

用drawdb.app可视化创建mysql关系表

平时自己建表,没有可视化图形参考为了便于理解,用drwadb画mysql关系表 drawDB | Online database diagram editor and SQL generator...

编程日记 2025/6/29 5:00:33

模型上下文协议（MCP）：AI的“万能插座”

~犬📰余~ “我欲贱而贵，愚而智，贫而富，可乎？ 曰：其唯学乎” 一、MCP解决什么问题？ \quad 在过去的几年中，AI大模型快速发展，从横空出世的GPT到“AI界拼多多”DeepSeek&am…...

编程日记 2025/6/29 2:39:38

初识 Pandas：Python 数据分析的利器

在数据分析、数据清洗和可视化等领域，Python 无疑是最受欢迎的语言之一，而在 Python 的数据处理生态中，Pandas 是最核心、最基础的库之一。如果你接触数据分析、机器学习、金融建模，或者只是想处理一些 Excel 表格，那么…...

编程日记 2025/6/29 1:37:18

Python教程（四）参数提取pymysql

Python（四） 本系列其他教程： Python教程(二)：函数、异常、模块&包、文件读取、常用模块 Python教程(三)：类&对象、闭包、装饰器、类型注解 Python教程(三)：类&对象、闭包、装饰器、类型注解、…...

编程日记 2025/7/8 1:01:41

Halcon案例(一):C#联合Halcon识别路由器上的散热孔

本案例分3部分识别效果,分别显示识别前后识别后;代码展示,分别是Halcon源码和Halcon转为C#的代码代码解释(解释在源码中) 原图如下: 处理后的图像: Halcon源码： *读取一张图像 read_image (Image, progres)*获取图像大小 get_image_size (Image, Width, Height)*关…...

编程日记 2025/6/29 1:37:15

SC5061串口设备联网服务器，4路RS-232，4路422/485串行接口

串口设备联网服务器，简称串口服务器。能够将RS-232/485/422串口设备联入TCP/IP网络，实现RS-232/485/422串口与TCP/IP网络接口的数据双向传输，使得串口设备能够具备联网功能，根据串口数量的不同，可以分为单串口、两串口…...

编程日记 2025/7/14 14:03:24

谈AI/OT 的融合

过去的十几年间，工业界讨论最多的话题之一就是IT/OT 融合，现在，我们不仅要实现IT/OT 的融合，更要面向AI/OT 的融合。看起来不太靠谱，却留给我们无限的想象空间。OT 领域的专家们不要再当“九斤老太”，指责这…...

编程日记 2025/6/29 1:39:16

RAGFlow 初步尝试 (01)

1. 起因， 目的: 简单尝试一下。 2. 先看效果 3. 过程: 目的: 研究 RAG 的实现过程。实用目的： 对于一本电子书， pdf，我在读书的时候，可以问一写些问题。对一个 github 项目，可以迅速理解文件的关系。…...

编程日记 2025/6/29 1:37:17

Linux 服务器用 SSH 拉取多个 Git 工程

在一台 Linux 服务器上用 SSH 拉取两个 Git 工程，而这两个工程对应的是不同的 Git 账号（SSH Key），做法： 使用 SSH Config 配置多个 Git 账号场景假设： 工程 A 的仓库地址：gitgithub.com:com…...

编程日记 2025/6/29 3:41:09

测试文章标题01

模型上下文协议（Model Context Protocol, MCP）深度解析一、MCP的核心概念模型上下文协议（Model Context Protocol, MCP）是一种用于规范机器学习模型与外部环境交互的标准化框架。其核心目标是通过定义统一的接口和数据格式&am…...

编程日记 2025/6/29 4:39:38

如何禁止chrome自动更新

百度了一下下面这个方法实测有效目录 1、WINR 输入 services.msc 2、在Services弹窗中找到下面两个service并disable 3、验证是否禁止更新成功： 1、WINR 输入 services.msc 2、在Services弹窗中找到下面两个service并disable GoogleUpdater InternalService…...

编程日记 2025/7/17 6:29:11

【C++重载操作符与转换】构造函数和复制控制

目录一、构造函数：对象的初始化引擎 1.1 构造函数的定义与分类 1.2 初始化列表：高效且安全的初始化方式 1.3 显式构造函数与类型安全二、复制控制：管理对象的生命周期 2.1 复制构造函数：深拷贝的核心 2.2 赋值运算符重载…...

编程日记 2025/6/29 1:39:31

CATIA高效工作指南——常规配置篇（二）

一、结构树（Specification Tree）操作技巧精讲结构树是CATIA设计中记录模型历史与逻辑关系的核心模块，其高效管理直接影响设计效率。本节从基础操作到高级技巧进行系统梳理。 1.1 结构树激活与移动激活方式： 白线…...

编程日记 2025/6/29 1:37:19

神经生物学+图论双buff，揭示大脑语言系统的拓扑结构

摘要近年来，神经影像数据分析的进展促进了大脑网络整合中适应性变化的表征。本研究提出了一种融合知识驱动与数据驱动的独特方法，为更精确地理解这些变化提供了新思路。通过运用图网络分析，并结合特定领域脑网络系统的现有神经生物学知识&am…...

编程日记 2025/6/29 2:20:55

Kotlin 懒初始化值

Kotlin 懒初始化值：深入理解 lateinit 与 by lazy 在 Kotlin 开发中，懒初始化（Lazy Initialization） 是一种常见的优化技巧，它允许我们将对象的初始化延迟到真正需要使用时再执行。Kotlin 提供了两种核心机制来实现懒…...

编程日记 2025/6/29 1:43:33

高速系统设计实例设计分析

在上几章的内容中，我们从纯粹高速信号的理论分析，到 Cadence 工具的具体使用都做了详细的讲解和介绍。相信读者通过前面章节的学习，已经对高速系统的设计理念及 Cadence 相应的设计流程和工具有了一个基本的认识。但是，对于高速电…...

编程日记 2025/6/29 4:45:11

数据结构与算法学习-JavaScript的Array.prototype.reduce()方法

一、语法 array.reduce(callbackfn, initialValue);callbackfn (accumulator, currentValue, currentIndex, array) > {// 回调逻辑 } callbackFn 为数组中每个元素执行的函数。其返回值将作为下一次调用 callbackFn 时的 accumulator 参数。对于最后一次调用&#xff0c…...

编程日记 2025/6/29 4:13:43

[Java][Leetcode simple] 189. 轮转数组

借助辅助数组借助一个辅助数组tmp保存后面k个元素然后逆序循环，使用数组前面n-k个元素覆盖最后到后面最后把前k个元素从tmp中拿回来public void rotate(int[] nums, int k) {int len nums.length;k k % len;int[] Ra new int[len];int cnt 0;for (int i len-k…...

编程日记 2025/6/29 1:39:32

Hadoop 的代理用户（Proxy User）功能解释

在$HADOOP_HOME/etc/hadoop下的core-site.xml 配置里，可以新增hadoop集群的代理用户。在集成配置中，会经常用到。它属于 Hadoop 安全机制的一部分。以下是对该配置效果的详细说明及示例： 配置效果 <!-- 允许用户 hadoop 从主机 hadoop…...

编程日记 2025/7/16 12:01:57

day06_java中的流程控制语句

流程控制语句 Java提供了一些流程控制语句，来控制程序的执行流程顺序结构任何编程语言中最常见的程序结构就是顺序结构顺序结构就是程序从上到下逐行地执行，中间没有任何判断和跳转如果main方法的多行代码之间没有任何流程控制，则程序总是…...

编程日记 2025/6/29 3:18:38

机器学习实战：归一化与标准化的选择指南

在机器学习实战中——是否需要归一化（Normalization）或标准化（Standardization），取决于所使用的模型类型。 ✅ LightGBM / XGBoost 是否需要归一化或标准化？ 不需要。 🔧 原因： L…...

编程日记 2025/6/29 1:44:24

【内蒙古】《内蒙古自治区本级政务信息化建设项目预算支出标准（试行）》（内财预〔2024〕1449号）-费用标准解读系列

内蒙古自治区政务服务与数据管理局在2024年11月29日发布了《内蒙古自治区本级政务信息化建设项目预算支出标准(试行)》（内财预〔2024〕1449号）。该文件适用于自治区本级各部门、单位非涉密政务信息化建设项目(以下简称建设项目)经费的预算编制、审核。下…...

编程日记 2025/6/29 4:02:20

文本数据可视化

目录【实验目的】【实验原理】【实验环境】【实验步骤】原理操作步骤图像展示【实验目的】了解什么是文本可视化掌握文本可视化的相关技术文本信息的提取和可视表达本次实验是将某一文本进行可视化生成词云图片尝试构造文本指纹【实验原理】…...

编程日记 2025/6/29 4:33:00

qt命名空间演示

#ifndef CIR_H #define CIR_Hnamespace cir {double PI3.141592653;//获取圆行周长double getLenthOfCircle(double radius){return 2*PI*radius;}//获取圆形面积double getAreaOfCircle(double radius){return PI*radius*radius;}} #endif // CIR_H#include <iostream> …...

编程日记 2025/6/29 3:34:20

Android学习总结之布局篇

一、大厂面试高频布局真题解析 1. ConstraintLayout vs RelativeLayout 深度对比真题问法： "为什么说 ConstraintLayout 是 RelativeLayout 的替代方案？两者在布局原理、性能、复杂场景处理上有什么核心区别？" 核心考点解析&am…...

编程日记 2025/6/29 2:28:53

星际篮球争霸赛/MVP争夺战 - 华为OD机试真题(A卷、Java题解)

华为OD机试题库《C》限时优惠 9.9 华为OD机试题库《Python》限时优惠 9.9 华为OD机试题库《JavaScript》限时优惠 9.9 针对刷题难，效率慢，我们提供一对一算法辅导， 针对个人情况定制化的提高计划（全称1V1效率更高）。看…...

编程日记 2025/6/29 1:39:25

RNN（循环神经网络）原理与结构

1 RNN（循环神经网络）原理与结构循环神经网络（Recurrent Neural Network, RNN）是一类专门用于处理序列数据（如时间序列、文本、语音等）的深度学习模型。与传统的前馈神经网络不同，RNN在每个时间…...

编程日记 2025/7/4 15:01:03

Claude深度解析：从技术原理到实战应用的全栈指南

🔥「炎码工坊」技术弹药已装填！点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】引言：AI编程新纪元中的Claude 在生成式AI技术爆发的2024年，Anthropic的Claude系列模型以卓越的长文本处理能力和精确的代码生成质量，正在重塑程序员的开发范式。当开发者…...

编程日记 2025/7/11 23:22:47

9.渐入佳境 -- 套接字的多种可选项

前言套接字具有多种特性，这些特性可通过可选项更改。本章将介绍更改套接字可选项的方法，并以此为基础进一步观察套接字内部。一、套接字可选项和I/O缓冲大小我们进行套接字编程时往往只关注数据通信，而忽略了套接字具有的不同特性。但是…...

编程日记 2025/6/29 4:58:16

AI日报 - 2024年05月13日

🌟 今日概览 (60秒速览) ▎🚀 技术突破 | Flow-GRPO将在线RL引入流匹配模型，提升性能并降低训练成本；「层内循环」(ILR)技术无需增加参数即可提升Transformer性能。▎💬 行业热议 | ICML强制作者参会政策引发广泛争议…...

编程日记 2025/6/29 2:21:43

开发工具分享: Web前端编码常用的在线编译器

1.OneCompiler 工具网址：https://onecompiler.com/ OneCompiler支持60多种编程语言，在全球有超过1280万用户，让开发者可以轻易实现代码的编写、运行和共享。 OneCompiler的线上调试功能完全免费，对编程语言的覆盖也很全&#x…...

编程日记 2025/6/29 3:39:44

Android学习总结之线程池篇

一、线程池参数调优实战真题真题 1：直播 APP 弹幕加载线程池设计题目描述：直播 APP 需要实时加载弹幕数据（网络请求，IO 密集型），同时渲染弹幕视图（UI 操作需切主线程）&#xff0…...

编程日记 2025/7/10 11:28:51

03.Golang 切片（slice）源码分析（二、append实现）

Golang 切片（slice）源码分析（二、append实现） 前言： Golang 切片（slice）源码分析（一、定义与基础操作实现） 在前面的文章我们介绍了，切片的结构体与创建\扩容…...

编程日记 2025/7/11 14:03:05

Python实例题：pygame开发打飞机游戏

目录 Python实例题题目 pygame-aircraft-game使用 Pygame 开发的打飞机游戏脚本代码解释初始化部分： 游戏主循环： 退出部分： 运行思路注意事项 Python实例题题目 pygame开发打飞机游戏 pygame-aircraft-game使用 Pygame 开发…...

编程日记 2025/7/16 21:54:31