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

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

方法一&#xff1a;字典树动态规划 首先,创建node类&#xff0c;每个对象应该包含:一个node array nexts(如果有通往’a’的路&#xff0c;那么对应的nexts[0]就不该为null); 一个boolean 变量&#xff08;如果到达的这个字母恰好是字典中某个候选串的结尾&#xff0c;那么 标记…...

基础学习——关于list、numpy、torch在float和int等数据类型转换方面的总结

系列文章目录 Numpy学习——创建数组及常规操作&#xff08;数组创建、切片、维度变换、索引、筛选、判断、广播&#xff09; Tensor学习——创建张量及常规操作&#xff08;创建、切片、索引、转换、维度变换、拼接&#xff09; 基础学习——numpy与tensor张量的转换 基础学习…...

华纳云美国Linux服务器常用命令分享

美国Linux服务器系统目前也是跟Windows操作系统一样用户量非常多&#xff0c;其简单的纯命令操作模式可以节省很多系统空间&#xff0c;本文小编就来分享一些美国Linux服务器系统常用的命令&#xff0c;希望能够给刚入门的美国Linux服务器系统的用户提供一些操作参考。 1、系统…...

【minio】8.x版本与SpringBoot版本不兼容报错

错误异常&#xff1a; <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&#xff09;初级-账号 对于新事物的出现&#xff0c;很多人对此都是抱着一个看热闹的态度&#xff0c;大家对于这个东西的整体认知水平是很低的&#xff01; 所以这个时候的思路就是快速去抢占市场&#xff0c;去各个平台发一些和ChatGPT相关的视频和文章去抢占市…...

【Go编程语言】流程控制

流程控制 文章目录 流程控制一、if 语句1.if 嵌套语句 二、switch 语句三、for 循环四、string 程序的流程控制结构一具有三种&#xff1a;顺序结构&#xff0c;选择结构&#xff0c;循环结构 顺序结构&#xff1a;从上到下&#xff0c;逐行执行。默认的逻辑 选择结构&#xf…...

Sql Server 自动备份

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

ThreadLocal的应用

1. ThreadLocal 是什么 JDK 对ThreadLocal的描述为&#xff1a; 此类提供线程局部变量。这些变量与普通变量的不同之处在于&#xff0c;每个访问一个变量的线程&#xff08;通过其get或set方法&#xff09;都有自己的、独立初始化的变量副本。ThreadLocal 实例通常是类中的私有…...

中值滤波_中值滤波原理

均值滤波是典型的线性滤波算法,它是指在图像上对目标像素给一个模板,该模板包括了其周围的临近像素(以目标象素为中心的周围8个象素,构成一个滤波模板,即去掉目标象素本身).再用模板中的全体像素的平均值来代替原来像素值.均值滤波也称为线性滤波,其采用的主要方法为领域平均法…...

day15 - 使用图像金字塔进行图像拼接

在我们之前的学习过程中&#xff0c;使用的都是恒定大小的图像&#xff0c;但是在某些情况下&#xff0c;我们需要使用不同分辨率的&#xff08;相同&#xff09;图像。例如&#xff0c;当在图像中搜索某些东西&#xff08;例如人脸&#xff09;时&#xff0c;我们不确定对象将…...

算法修炼之筑基篇——筑基一层初期(解决01背包问题)

✨博主&#xff1a;命运之光 ✨专栏&#xff1a;算法修炼之练气篇​​​​​ ✨博主的其他文章&#xff1a;点击进入博主的主页 前言&#xff1a;学习了算法修炼之练气篇想必各位蒟蒻们的基础已经非常的扎实了&#xff0c;下来我们进阶到算法修炼之筑基篇的学习。筑基期和练气期…...

JVM的空间结构

目录 一、概述 二、分类 1.程序计数器区域(Program Counter Register)&#xff1a; 2.Java虚拟机栈(Stack)&#xff1a; 3.堆区(Heap)&#xff1a; 4.方法区(Method Area)&#xff1a; 5.本地方法栈(Native Method Stack)&#xff1a; 一、概述 JVM分为5个主要区域&…...

图像分割的常用算法

图像分割是指将一幅图像划分成多个子区域或像素集合的过程&#xff0c;其中每个子区域或像素集合具有一定的统计特征或语义信息。图像分割是图像处理中的基础任务&#xff0c;其应用涵盖了医学影像、计算机视觉、机器人技术等多个领域。常用的图像分割算法包括&#xff1a; 1.…...

AI歌手真的可以吗

你听过AI歌手吗&#xff1f;近日&#xff0c;“AI孙燕姿”火遍全网&#xff0c;AI孙燕姿翻唱林俊杰的《她说》、周董的《爱在西元前》、赵雷的《成都》等等歌曲让网友听了直呼&#xff1a;“听了一晚上&#xff0c;出不去了。”你认为AI歌手会取代流行歌手成为主流吗&#xff1…...

Kubernetes高级存储

Kubernetes高级存储 PV PVC k8s支持的存储系统很多&#xff0c;全部掌握不现实。为了屏蔽底层存储实现的细节&#xff0c;方便用户使用&#xff0c;k8s引入PV和PVC两种资源对象。 PV(Persistent Volume)持久化卷&#xff0c;对底层共享存储的抽象&#xff0c;一般由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和文心一言接连发布&#xff0c;AI工具已经开始走进千家万户。 拿文心一言发布会上的几个问题调戏了 GPT4 一下&#xff0c;看看表现如何。 第一个为文心的回答&#xff0c;第二个为GPT4 的回答。 1. 可以总结一下三体的核心内容吗&#xf…...

Tcl-5. format 命令

format 命令和 C 语言中的 printf 和 sprintf 命令类似。它根据一组格式说明来格式化字符 串。此命令不会改变被操作字符串的内容。 [语法]&#xff1a;format spec value1 value2 ... spec 变元包含了格式说明关键词和附加文字。使用%来引入一个关键词&#xff0c;后跟 0 个…...

BloombergGPT: 首个金融垂直领域大语言模型

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

CMake深度解析:掌握add_custom_command,精通Makefile生成规则

CMake深度解析&#xff1a;掌握add_custom_command&#xff0c;精通Makefile生成规则 1. CMake简介与基础知识1.1 CMake的基本概念&#xff08;CMake Basic Concepts&#xff09;1.1.1 项目&#xff08;Project&#xff09;1.1.2 目标&#xff08;Target&#xff09;1.1.3 命令…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...