leetCode !! word break
方法一:字典树+动态规划
首先,创建node类,每个对象应该包含:一个node array nexts(如果有通往’a’的路,那么对应的nexts[0]就不该为null); 一个boolean 变量(如果到达的这个字母恰好是字典中某个候选串的结尾,那么 标记end=true);
然后,根据 字典,建立字典树;
接着,使用动态规划的方式,检查目标字符串str是否可以用字典中的候选串拼出来。具体地,dp[i]表示 str[i…] 是否可以用字典中的候选串拼出来。对于str[i…],枚举第一子串该如何划分,str[i…end]中end可取值i,i+1,…。检查str[i…end]是否在字典中,对应地余下str[end+1,…]是否也可以 用字典中的候选串拼出来,即dp[end+1]==true么? 二者都成立说明 str[i…]可以用字典中的候选串拼出来, 即dp[i]==true.对于str[i…]来说,只要找到一种拼接方式即可,于是break,去枚举下一个str[i-1,…]是否可以用字典中的候选串拼出来。
public boolean wordBreak(String word, List<String> dict){// build a treeNode root = new Node();for(String s:dict){Node cur = root;int index=0;char[] str = s.toCharArray();for(char c:str){index = c-'a';if(cur.nexts[index]==null){cur.nexts[index]=new Node();}cur = cur.nexts[index];}cur.end=true;}// checkchar[] chs = word.toCharArray();// dp[i]int n= chs.length;boolean[] dp = new boolean[n+1];dp[n]=true;// !!// if str[i..n-1] can be done, //then obviously dp[i] = str[i...n-1]&&dp[n] = true; // so dp[n] should be true;for(int i=n-1;i>=0;i--){Node cur = root;for(int end=i;end<n;end++){int index = chs[end]-'a';if(cur.nexts[index]==null) {break;// 剪枝,避免了无效的枚举}cur = cur.nexts[index];if(cur.end&&dp[end+1]){dp[i]=true;break;}}}return dp[0];}
方法2: 递归函数+哈希表
写一个递归函数 str[index…] ,以字典为标本,有多少种分解方式.
注:在力扣上做测试,它超过了时间限制。
public static boolean wordBreak(String s, List<String> wordDict) {return process(s, 0, new HashSet<>(wordDict)) != 0;}// s[0......index-1]这一段,已经分解过了,不用在操心// s[index.....] 这一段字符串,能够被分解的方法数,返回public static int process(String s, int index, HashSet<String> wordDict) {if (index == s.length()) {// this cutting pattern is acceptedreturn 1;}// index没到最后// index...index// index...index+1// index....index+2// index....endint ways = 0;for (int end = index; end < s.length(); end++) {// s[index....end]String pre = s.substring(index, end + 1);if (wordDict.contains(pre)) {ways += process(s, end + 1, wordDict);}}return ways;}
方法三:动态规划+哈希表
在方法一的基础上,把字典树换成哈希表。
运行效率上,显然不如用字典树的方法一。这主要是因为方法一中间遇到不在Trie上的字符就break,进入下一个开头的尝试,这可以视为一种“剪枝”,避免不必要的操作。
而,这里使用哈希表,只要用substring函数切出来的,都检查他是否在哈希表中,所以费时。
public boolean wordBreak(String word,List<String> dict){int n = word.length();char[] str = word.toCharArray();boolean[] dp = new boolean[n+1];dp[n]=true;HashSet<String> set = new HashSet<>(dict);for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(set.contains(word.substring(i, j+1))&&dp[j+1]){dp[i] = true;}}}return dp[0];}
相关文章:
leetCode !! word break
方法一:字典树动态规划 首先,创建node类,每个对象应该包含:一个node array nexts(如果有通往’a’的路,那么对应的nexts[0]就不该为null); 一个boolean 变量(如果到达的这个字母恰好是字典中某个候选串的结尾,那么 标记…...

基础学习——关于list、numpy、torch在float和int等数据类型转换方面的总结
系列文章目录 Numpy学习——创建数组及常规操作(数组创建、切片、维度变换、索引、筛选、判断、广播) Tensor学习——创建张量及常规操作(创建、切片、索引、转换、维度变换、拼接) 基础学习——numpy与tensor张量的转换 基础学习…...
华纳云美国Linux服务器常用命令分享
美国Linux服务器系统目前也是跟Windows操作系统一样用户量非常多,其简单的纯命令操作模式可以节省很多系统空间,本文小编就来分享一些美国Linux服务器系统常用的命令,希望能够给刚入门的美国Linux服务器系统的用户提供一些操作参考。 1、系统…...
【minio】8.x版本与SpringBoot版本不兼容报错
错误异常: <minio.version>8.4.3</minio.version><spring-boot.version>2.6.13</spring-boot.version>Description:An attempt was made to call a method that does not exist. The attempt was made from the following location:io.min…...

如何用chatGPT赚钱?
赚钱思路 1)初级-账号 对于新事物的出现,很多人对此都是抱着一个看热闹的态度,大家对于这个东西的整体认知水平是很低的! 所以这个时候的思路就是快速去抢占市场,去各个平台发一些和ChatGPT相关的视频和文章去抢占市…...

【Go编程语言】流程控制
流程控制 文章目录 流程控制一、if 语句1.if 嵌套语句 二、switch 语句三、for 循环四、string 程序的流程控制结构一具有三种:顺序结构,选择结构,循环结构 顺序结构:从上到下,逐行执行。默认的逻辑 选择结构…...

Sql Server 自动备份
Sql Server 自动备份 文章目录 Sql Server 自动备份1. 打开SQL Server,在管理下找到”维护计划”,右键点击”维护计划向导”,如图;2. 再次点击维护计划向导3. 在选择维护任务下勾选”备份数据库”、”清楚维护任务”4.选择需要备份…...

ThreadLocal的应用
1. ThreadLocal 是什么 JDK 对ThreadLocal的描述为: 此类提供线程局部变量。这些变量与普通变量的不同之处在于,每个访问一个变量的线程(通过其get或set方法)都有自己的、独立初始化的变量副本。ThreadLocal 实例通常是类中的私有…...
中值滤波_中值滤波原理
均值滤波是典型的线性滤波算法,它是指在图像上对目标像素给一个模板,该模板包括了其周围的临近像素(以目标象素为中心的周围8个象素,构成一个滤波模板,即去掉目标象素本身).再用模板中的全体像素的平均值来代替原来像素值.均值滤波也称为线性滤波,其采用的主要方法为领域平均法…...

day15 - 使用图像金字塔进行图像拼接
在我们之前的学习过程中,使用的都是恒定大小的图像,但是在某些情况下,我们需要使用不同分辨率的(相同)图像。例如,当在图像中搜索某些东西(例如人脸)时,我们不确定对象将…...

算法修炼之筑基篇——筑基一层初期(解决01背包问题)
✨博主:命运之光 ✨专栏:算法修炼之练气篇 ✨博主的其他文章:点击进入博主的主页 前言:学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了,下来我们进阶到算法修炼之筑基篇的学习。筑基期和练气期…...
JVM的空间结构
目录 一、概述 二、分类 1.程序计数器区域(Program Counter Register): 2.Java虚拟机栈(Stack): 3.堆区(Heap): 4.方法区(Method Area): 5.本地方法栈(Native Method Stack): 一、概述 JVM分为5个主要区域&…...
图像分割的常用算法
图像分割是指将一幅图像划分成多个子区域或像素集合的过程,其中每个子区域或像素集合具有一定的统计特征或语义信息。图像分割是图像处理中的基础任务,其应用涵盖了医学影像、计算机视觉、机器人技术等多个领域。常用的图像分割算法包括: 1.…...
AI歌手真的可以吗
你听过AI歌手吗?近日,“AI孙燕姿”火遍全网,AI孙燕姿翻唱林俊杰的《她说》、周董的《爱在西元前》、赵雷的《成都》等等歌曲让网友听了直呼:“听了一晚上,出不去了。”你认为AI歌手会取代流行歌手成为主流吗࿱…...

Kubernetes高级存储
Kubernetes高级存储 PV PVC k8s支持的存储系统很多,全部掌握不现实。为了屏蔽底层存储实现的细节,方便用户使用,k8s引入PV和PVC两种资源对象。 PV(Persistent Volume)持久化卷,对底层共享存储的抽象,一般由k8s管理员进…...

云原生之使用Docker部署docker-compose-ui工具
云原生之使用Docker部署docker-compose-ui工具 一、Docker Compose UI介绍二、检查本地docker环境1.检查系统版本2.检查docker状态 三、下载Docker Compose UI镜像四、部署Docker Compose UI服务1.新建安装目录2.创建Docker Compose UI容器3.检查Docker Compose UI容器状态4.查…...

文心一言 vs GPT4
本周真是科技爱好者的狂欢节。GPT4和文心一言接连发布,AI工具已经开始走进千家万户。 拿文心一言发布会上的几个问题调戏了 GPT4 一下,看看表现如何。 第一个为文心的回答,第二个为GPT4 的回答。 1. 可以总结一下三体的核心内容吗…...
Tcl-5. format 命令
format 命令和 C 语言中的 printf 和 sprintf 命令类似。它根据一组格式说明来格式化字符 串。此命令不会改变被操作字符串的内容。 [语法]:format spec value1 value2 ... spec 变元包含了格式说明关键词和附加文字。使用%来引入一个关键词,后跟 0 个…...

BloombergGPT: 首个金融垂直领域大语言模型
BloombergGPT: 首个金融垂直领域大语言模型 Bloomberg 刚刚发布了一篇研究论文,详细介绍了他们最新的突破性技术 BloombergGPT。BloombergGPT是一个大型生成式人工智能模型,专门使用大量金融数据进行了训练,以支持金融行业自然语言处理 (NLP…...

CMake深度解析:掌握add_custom_command,精通Makefile生成规则
CMake深度解析:掌握add_custom_command,精通Makefile生成规则 1. CMake简介与基础知识1.1 CMake的基本概念(CMake Basic Concepts)1.1.1 项目(Project)1.1.2 目标(Target)1.1.3 命令…...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...

Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...

STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...