leetcode-140. 单词拆分 II (字典树/dp + 回溯法) + 字节测开字典树算法题

2024-03-06 21:40

本文主要是介绍leetcode-140. 单词拆分 II (字典树/dp + 回溯法) + 字节测开字典树算法题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明:

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1:

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]
示例 2:

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3:

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

两种思路做,第一种dp+回溯,第二种字典树+回溯。

方法一:dp+回溯法

image.png

这种思路是基于139.单词拆分 而来的,题意大概是给定的模式串能够被给定的非空单词列表wordDict拆分出来,dp的思想类似于求构成指定金额的钱币的不同组合。从前向后遍历利用一个一维数组不断更新当前金额情况下,上一次迭代的结果+当前金额减去当前钱币的大小的金额时的种类数目,状态转移为:dp[j] += dp[j-coins[i]]。那么用到单词拆分中时,dp[i]代表0~i-1长度的字符串是否能够由单词列表的单词构成(boolean),因此首先截取以i-1结尾,向前推当前单词列表长度个字符去比较,如果相同,那么就用到上面凑钱币的思想,使用dp[i] |= dp[i-len]的转移方程去更新当前状态 。

由于我们获取得dp数组代表的是前缀可被拆分的可能性,因此我们从后面开始对出现在单词列表中的单词开始进行深度优先遍历。如上图的状态(网站复制过来的),第一个递归过程只有一个节点,然后apple的前面又出现了两种拼接情况,于是这就需要我们使用一个双端队列Deque对整个递归的过程进行回溯的操作。在回溯的过程中,如果发现从尾部截取的字符串出现在单词列表中,并且出去该字符串的剩余部分字符串还可以由单词列表组成(利用上面的dp数组)的时候,就进行递归操作。

注意:使用双端队列因为是从尾部开始递归,所以根据题意,回溯的操作是需要使用一个头插的容器来辅助的。

这篇关于leetcode-140. 单词拆分 II (字典树/dp + 回溯法) + 字节测开字典树算法题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/781443

相关文章

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Java实现按字节长度截取字符串

《Java实现按字节长度截取字符串》在Java中,由于字符串可能包含多字节字符,直接按字节长度截取可能会导致乱码或截取不准确的问题,下面我们就来看看几种按字节长度截取字符串的方法吧... 目录方法一:使用String的getBytes方法方法二:指定字符编码处理方法三:更精确的字符编码处理使用示例注意事项方

基于Python打造一个智能单词管理神器

《基于Python打造一个智能单词管理神器》这篇文章主要为大家详细介绍了如何使用Python打造一个智能单词管理神器,从查询到导出的一站式解决,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 项目概述:为什么需要这个工具2. 环境搭建与快速入门2.1 环境要求2.2 首次运行配置3. 核心功能使用指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh