LeetCode 212.单词搜索II
https://leetcode.cn/problems/word-search-ii/description/?envType=study-plan-v2&envId=top-interview-150
文章目录
- 题目描述
- 解题思路
- 代码实现
题目描述
给定一个 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中的所有单词存起来,同时为了便于查找子节点,我们的字典树实现的时候,可以把子节点的实现方式换位HashMap<Integer, String>这样可以实现快速查找,而且可以按需建立子节点
然后对我们的board进行dfs遍历,查找当前遍历的字符串是否在字典树中
- 剪枝:每当当前访问的节点不是字典树中的任意一个单词的前缀,剪掉
- 去重:同一个单词可能在多个不同的路径出现,所以使用哈希集合对结果去重。
- dfs遍历当前节点之前,可以修改当前节点为’#', 遍历完在恢复
- 优化:删除匹配的单词,考虑以下情况。假设给定一个所有单元格都是 a 的二维字符网格和单词列表 [“a”, “aa”, “aaa”, “aaaa”] 。当我们使用方法一来找出所有同时在二维网格和单词列表中出现的单词时,我们需要遍历每一个单元格的所有路径,会找到大量重复的单词。
代码实现
class Solution {int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};public List<String> findWords(char[][] board, String[] words) {Trie trie = new Trie();for(String word: words) { // 插入字典树trie.insert(word);}Set<String> ans = new HashSet<String>(); // 结果集去重for(int i=0; i<board.length; i++){for(int j=0; j<board[0].length; j++){dfs(board, trie,i,j,ans); // dfs}}return new ArrayList<String>(ans);}public void dfs(char[][] board, Trie now , int i1, int j1, Set<String> ans){if(!now.children.containsKey(board[i1][j1])){ // 剪枝return;}char ch = board[i1][j1];now = now.children.get(ch);if(!"".equals(now.word)){ans.add(now.word);now.word = ""; // 优化,这样省的去重}board[i1][j1] = '#';for(int[] dir: dirs){int i2 = i1 + dir[0];int j2 = j1 + dir[1];if(i2 >= 0 && i2 < board.length && j2 >= 0 && j2 < board[0].length){dfs(board, now, i2, j2, ans);}}board[i1][j1] = ch;}
}class Trie{String word;Map<Character, Trie> children; // 子节点实现方式换位hashMap// boolean isWord; // 这里暂时没用public Trie(){this.word = "";this.children = new HashMap<Character, Trie>();}public void insert(String word){Trie cur = this;for(int i=0; i< word.length(); i++){char c = word.charAt(i);if(!cur.children.containsKey(c)){cur.children.put(c, new Trie());}cur = cur.children.get(c);}cur.word = word;}
}
相关文章:
LeetCode 212.单词搜索II
https://leetcode.cn/problems/word-search-ii/description/?envTypestudy-plan-v2&envIdtop-interview-150 文章目录 题目描述解题思路代码实现 题目描述 给定一个 m x n 二维字符网格 board 和一个单词(字符串)列表 words, 返回所有二…...
android 蓝牙技术 学习记录
一 。蓝牙介绍 蓝牙可以分为 经典蓝牙-----》传统蓝牙(BT 1.0/2.0/2.1)和高速蓝牙(BT3.0) 低功耗蓝牙 ----》BLE(BLE 4.0/4.1/4.2/5.0./5.1/5.2)和 Bluetooth Mesh 关于蓝牙协议。除开Mesh大致可以分为3层: App:上层协议有很多,例如ANP,HOGP,FTMP 等等 host:中…...
2024数维杯数学建模B题完整论文讲解(含每一问python代码+结果+可视化图)
大家好呀,从发布赛题一直到现在,总算完成了2024数维杯数学建模挑战赛生物质和煤共热解问题的研究完整的成品论文。 本论文可以保证原创,保证高质量。绝不是随便引用一大堆模型和代码复制粘贴进来完全没有应用糊弄人的垃圾半成品论文。 B题论…...
二叉树进阶 --- 中
目录 1. find 的递归实现 2. insert 的递归实现 3. erase 的递归实现 3.1. 被删除的节点右孩子为空 3.2. 被删除的节点左孩子为空 3.3. 被删除的节点左右孩子都不为空 4. 析构函数的实现 5. copy constructor的实现 6. 赋值运算符重载 7. 搜索二叉树的完整实现 1. fi…...
ChatGPT DALL-E绘图,制作各种表情包,实现穿衣风格的自由切换
DALL-E绘图功能探索: 1、保持人物形象一致,适配更多的表情、动作 2、改变穿衣风格 3、小女孩的不同年龄段展示 4、不同社交平台的个性头像创作 如果不会写代码,可以问GPT。使用地址:我的GPT4 视频,B站会发&#…...
程序环境和预处理、编译链接过程、编译的几个阶段、运行环境、预定义符号等的介绍
文章目录 前言一、程序的翻译环境和执行环境二、编译链接过程三、编译的几个阶段四、运行环境五、预定义符号总结 前言 程序环境和预处理、编译链接过程、编译的几个阶段、运行环境、预定义符号的介绍。 一、程序的翻译环境和执行环境 在 ANSI C 的任何一种实现中,…...
MySQL导入导出详细教程
导出 语法 mysqldump [OPTIONS] database [tables] mysqldump [OPTIONS] --databases [OPTIONS] DB1 [DB2 DB3...] mysqldump [OPTIONS] --all-databases [OPTIONS]导出所有数据库 mysqldump -uroot -proot --all-databases >/tmp/all.sql导出db1、db2两个数据库的所有数…...
STM32F103学习笔记 | 8. 二,八,十,十六进制表示方式
文章目录 进制基本信息参考文献 进制基本信息 C语言中的表示,前缀加0表示八进制数,前缀加0x表示十六进制数 基数数码名称描述代码和书本中的表示举例20 和 1二进制逢二进一,几乎所有的电子计算机内部都使用二进位制,分别为“0”…...
ROS2 工作空间
文章目录 ROS2 工作空间创建工作空间自动安装依赖编译工作空间设置环境变量参考链接 ROS2 工作空间 工作空间可以简单理解为工程目录。 ROS 系统中一个典型的工作空间结构如图所示: dev_ws: 根目录,里面会有四个子目录(子空间&a…...
基于CCS5.5的双音多频(DTMF)信号检测仿真实验(①检测型音频文件②输入生成音频并检测)
DTMF的优点 我们知道,DTMF根本上仍然是频谱分析,基础还是DFT,但DFT通常需要对一整段数据做变换,而DTMF不同,每输入一个采样点就计算一次,更有利于硬件实现。 基于CCS的双音多频(DTMF)信号检测原理 公式详细推导 详细的公式推导在下面这篇博客中已经进行了详细的描述,…...
Postgresql中JIT函数能否inline的依据function_inlinable
相关 《Postgresql源码(128)深入分析JIT中的函数内联llvm_inline》 《LLVM的ThinLTO编译优化技术在Postgresql中的应用》 前置阅读:《Postgresql源码(128)深入分析JIT中的函数内联llvm_inline》 在JIT inline函数的过…...
存储过程作为初始化数据例子
查询出每个人员,为每个人员插入11条数据,作为初始化数据 oracle存储过程 CREATE OR REPLACE PROCEDURE initialize_order_warn_config ISv_id NUMBER; BEGINSELECT COALESCE(MAX(id), 0) INTO v_id FROM order_warn_config;FOR rec IN (SELECT DISTINCT…...
【数据分析】 JupyterNotebook安装及使用简介
各位大佬好 ,这里是阿川的博客 , 祝您变得更强 个人主页:在线OJ的阿川 大佬的支持和鼓励,将是我成长路上最大的动力 阿川水平有限,如有错误,欢迎大佬指正 在数据分析中,一般用Pycharm编辑代…...
nginx命令大全
以下是Nginx的一些常用命令,适用于Linux环境,部分命令在Windows系统下也适用,但命令形式可能有所不同: 查看Nginx版本号: nginx -v:简短显示版本号。nginx -V:详细显示版本号及编译配置信息。 启动Nginx…...
【数据结构】顺序表与链表的差异
顺序表和链表都是线性表,它们有着相似的部分,但是同时也有着很大的差异。 存储空间上的差异: 对于插入上的不同点,顺序表在空间不够时需要扩容,而如果在使用realloc函数去扩容,会有原地扩容和异地扩容两种情…...
小程序如何进行评分评价
小程序以其便捷、快速、无需安装的特点,成为了众多企业、品牌与消费者之间的重要连接桥梁。而评价评分机制,作为小程序中不可或缺的一环,对于提升用户体验、建立用户信任、促进商家与用户的互动等方面,都具有至关重要的意义。本文…...
【MATLAB源码-第206期】基于matlab的差分进化算法(DE)机器人栅格路径规划,输出做短路径图和适应度曲线。
操作环境: MATLAB 2022a 1、算法描述 差分进化算法(Differential Evolution, DE)是一种有效的实数编码的进化算法,主要用于解决实值函数的全局优化问题。本文将详细介绍差分进化算法的背景、原理、操作步骤、参数选择以及实际应…...
Python图形界面(GUI)Tkinter笔记(三):控件的定位(1)
Tkinter(GUI)设计图形界面时有三种控件的包装方法去定位各控件在窗口(父容器、根窗口)上的位置。 【1】pack()方法:用方位来定位位置,类似于Word文档中的文字对齐方式。 【2】grid()方法:用二维表格式的坐标值定位,类似于EXCEL单位元。 【3】place()方法:用窗口的像…...
数据结构--单链表 详解(附代码
目录: 1:链表的概念及结构 2:实现单链表 3:常见疑问 解答 (看到最后!!) 一:链表的概念及结构 1.1 概念: 链表是⼀种 物理存储结构上非连续、非顺序的 存储结…...
leetcode 1749.任意子数组和的绝对值的最大值
思路:dp 说到绝对值,大家肯定不陌生,但是用在dp上就会使问题变得稍微复杂一些了。 我们在最大子数组和的那道题中知道,在状态转移的时候,我们会舍弃掉为负数的连续部分,重新构建连续的子串。但是…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)
本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡
何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践,很多人以为AI已经强大到不需要程序员了,其实不是,AI更加需要程序员,普通人…...
2025-05-08-deepseek本地化部署
title: 2025-05-08-deepseek 本地化部署 tags: 深度学习 程序开发 2025-05-08-deepseek 本地化部署 参考博客 本地部署 DeepSeek:小白也能轻松搞定! 如何给本地部署的 DeepSeek 投喂数据,让他更懂你 [实验目的]:理解系统架构与原…...
零基础在实践中学习网络安全-皮卡丘靶场(第十一期-目录遍历模块)
经过前面几期的内容我们学习了很多网络安全的知识,而这期内容就涉及到了前面的第六期-RCE模块,第七期-File inclusion模块,第八期-Unsafe Filedownload模块。 什么是"遍历"呢:对学过一些开发语言的朋友来说应该知道&…...
