Leetcode 3213. Construct String with Minimum Cost
- Leetcode 3213. Construct String with Minimum Cost
- 1. 解题思路
- 2. 代码实现
- 题目链接:3213. Construct String with Minimum Cost
1. 解题思路
这一题的话思路上还是比较直接的,就是一个trie树加一个动态规划,通过trie树来快速寻找每一个位置作为起点时能够匹配的全部字符串,然后用一个动态规划来获取最优剪切方案。
其中,关于trie树的内容可以参考我之前的博客《经典算法:Trie树结构简介》,这里就不过多展开了。
然后当前的实现其实还蛮暴力的,时间上勉勉强强通过了全部测试样例,不过应该可以通过剪枝以及优化trie树内的内容来进行一下优化,有兴趣的读者可以考虑一下其具体实现,这里就不过多进行展开了。
2. 代码实现
给出python代码实现如下:
class Trie:def __init__(self):self.trie = {}def add_word(self, word, cost):trie = self.triefor c in word:trie = trie.setdefault(c, {})if "eos" not in trie:trie["eos"] = (word, cost)elif cost < trie["eos"][1]:trie["eos"] = (word, cost)returndef find_all_prefix(self, word):prefixs = []trie = self.triefor c in word:if c not in trie:breaktrie = trie[c]if "eos" in trie:prefixs.append(trie["eos"])return prefixsclass Solution:def minimumCost(self, target: str, words: List[str], costs: List[int]) -> int:trie = Trie()for word, cost in zip(words, costs):trie.add_word(word, cost)n = len(target)ans = math.inf@lru_cache(None)def dp(idx):nonlocal ansif idx >= n:return 0prefixs = trie.find_all_prefix(target[idx:])if prefixs == []:return math.infreturn min(c + dp(idx+len(w)) for w, c in prefixs)ans = dp(0)return ans if ans != math.inf else -1
提交代码评测得到:耗时10897ms,占用内存267.2MB。
相关文章:
Leetcode 3213. Construct String with Minimum Cost
Leetcode 3213. Construct String with Minimum Cost 1. 解题思路2. 代码实现 题目链接:3213. Construct String with Minimum Cost 1. 解题思路 这一题的话思路上还是比较直接的,就是一个trie树加一个动态规划,通过trie树来快速寻找每一个…...
python操作SQLite3数据库进行增删改查
python操作SQLite3数据库进行增删改查 1、创建SQLite3数据库 可以通过Navicat图形化软件来创建: 2、创建表 利用Navicat图形化软件来创建: 存储在 SQLite 数据库中的每个值(或是由数据库引擎所操作的值)都有一个以下的存储类型: NULL. 值是空值。 INTEGER. 值是有符…...
【电控笔记6.7】非最小相位系统
全通滤波器 [...
Day05-04-持续集成总结
Day05-04-持续集成总结 1. 持续集成2. 代码上线目标项目 1. 持续集成 git 基本使用, 拉取代码,上传代码,分支操作,tag标签 gitlab 用户 用户组 项目 , 备份,https,优化. jenkins 工具平台,运维核心, 自由风格工程,maven风格项目,流水线项目, 流水线(pipeline) mavenpom.xmlta…...
PyQt5动态热力图清空画布关闭ColorBar
PyQt5生成正弦波动态热力图清空画布关闭ColorBar 1、简介 生成随机正弦波,使用pyqtgraph展示出来,并且使用热力图展示不同频率的正弦波,使用不同的画布颜色显示热力图的变化。 使用python3.8 导入库: pip install matplotlib==3.7.5 pip install numpy==1.24.4 pip in…...
python爬虫入门(一)之HTTP请求和响应
一、爬虫的三个步骤(要学习的内容) 1、获取网页内容 (HTTP请求、Requests库) 2、解析网页内容 (HTML网页结构、Beautiful Soup库) 3、存储或分析数据 b站学习链接: 【【Python爬虫】爆肝两…...
华为OD机考题(HJ41 称砝码)
前言 经过前期的数据结构和算法学习,开始以OD机考题作为练习题,继续加强下熟练程度。有需要的可以同步练习下。 描述 现有n种砝码,重量互不相等,分别为 m1,m2,m3…mn ; 每种砝码对应的数量为 x1,x2,x3...xn 。现在要…...
Qt涂鸦板
Qt版本:Qt6 具体代码: 头文件 dialog.h #ifndef DIALOG_H #define DIALOG_H#include <QDialog>QT_BEGIN_NAMESPACE namespace Ui { class Dialog; } QT_END_NAMESPACEclass Dialog : public QDialog {Q_OBJECTpublic:Dialog(QWidget *parent n…...
C++_03
1、构造函数 1.1 什么是构造函数 类的构造函数是类的一种特殊的成员函数,它会在每次创建类的新对象时执行。 每次构造的是构造成员变量的初始化值,内存空间等。 构造函数的名称与类的名称是完全相同的,并且不会返回任何类型,也不…...
强化学习中的Double DQN、Dueling DQN和PER DQN算法详解及实战
1. 深度Q网络(DQN)回顾 DQN通过神经网络近似状态-动作值函数(Q函数),在训练过程中使用经验回放(Experience Replay)和固定目标网络(Fixed Target Network)来稳定训练过程…...
前端八股文 说一说样式优先级的规则是什么?
标准的回答 CSS样式的优先级应该分成四大类 第一类 !important: 😄无论引入方式是什么,选择器是什么,它的优先级都是最高的。 第二类 引入方式: 😄行内样式的优先级要高于嵌入和外链,嵌入和外链…...
洞察国内 AI 绘画行业的璀璨前景
在科技的浪潮中,AI 绘画如同一颗璀璨的新星,正在国内的艺术与技术领域绽放出耀眼的光芒。 近年来,国内 AI 绘画行业发展迅猛,展现出巨大的潜力。随着人工智能技术的不断突破,AI 绘画算法日益精进,能够生成…...
socket编程
文章目录 套接字网路字节序列TCP和UDP套接字 本文章主要介绍Linux下套接字的相关接口,和一些基础知识。 套接字 所有网络通信的行为本质都是进程间进行通信,网络通信也是进程间通信,只不过是不同主机上的两个进程之间的通信。网络通信对于双…...
python自动移除excel文件密码(升级v2版本)
欢迎查看第一版 https://blog.csdn.net/weixin_45631815/article/details/140013476?spm1001.2014.3001.5502 一功能改进 此版本主要改进功能有以下: 直接可以调用函数实现可以尝试多个密码没有加密的文件进行保存,可以按实际业务进行改进.思路来源:java 面向对象设计模式.…...
深入MOJO编程语言的单元测试世界
引言 在软件开发的历程中,单元测试扮演着至关重要的角色。单元测试不仅帮助开发者确保代码的每个部分都按预期工作,而且也是代码质量和维护性的关键保障。本文将引导读者了解如何在MOJO这一假想编程语言中编写单元测试,尽管MOJO并非真实存在…...
Canvas:掌握颜色线条与图像文字设置
想象一下,用几行代码就能创造出如此逼真的图像和动画,仿佛将艺术与科技完美融合,前端开发的Canvas技术正是这个数字化时代中最具魔力的一环,它不仅仅是网页的一部分,更是一个无限创意的画布,一个让你的想象…...
打包导入pyzbar的脚本时的注意事项
目录 前言问题问题的出现解决 总结 本文由Jzwalliser原创,发布在CSDN平台上,遵循CC 4.0 BY-SA协议。 因此,若需转载/引用本文,请注明作者并附原文链接,且禁止删除/修改本段文字。 违者必究,谢谢配合。 个人…...
02-android studio实现下拉列表+单选框+年月日功能
一、下拉列表功能 1.效果图 2.实现过程 1)添加组件 <LinearLayoutandroid:layout_width"match_parent"android:layout_height"wrap_content"android:layout_marginLeft"20dp"android:layout_marginRight"20dp"android…...
曹操的五色棋布阵 - 工厂方法模式
定场诗 “兵无常势,水无常形,能因敌变化而取胜者,谓之神。” 在三国的战场上,兵法如棋,布阵如画。曹操的五色棋布阵,不正是今日软件设计中工厂方法模式的绝妙写照吗?让我们从这个神奇的布阵之…...
谷粒商城学习笔记-逆向工程错误记录
文章目录 1,Since Maven 3.8.1 http repositories are blocked.1.1 在maven的settings.xml文件中,新增如下配置:1.2,执行clean命令刷新maven配置 2,internal java compiler error3,启动逆向工程报错&#x…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
VisualXML全新升级 | 新增数据库编辑功能
VisualXML是一个功能强大的网络总线设计工具,专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑(如DBC、LDF、ARXML、HEX等),并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...
