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

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. 代码实现 题目链接&#xff1a;3213. Construct String with Minimum Cost 1. 解题思路 这一题的话思路上还是比较直接的&#xff0c;就是一个trie树加一个动态规划&#xff0c;通过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请求和响应

一、爬虫的三个步骤&#xff08;要学习的内容&#xff09; 1、获取网页内容 &#xff08;HTTP请求、Requests库&#xff09; 2、解析网页内容 &#xff08;HTML网页结构、Beautiful Soup库&#xff09; 3、存储或分析数据 b站学习链接&#xff1a; 【【Python爬虫】爆肝两…...

华为OD机考题(HJ41 称砝码)

前言 经过前期的数据结构和算法学习&#xff0c;开始以OD机考题作为练习题&#xff0c;继续加强下熟练程度。有需要的可以同步练习下。 描述 现有n种砝码&#xff0c;重量互不相等&#xff0c;分别为 m1,m2,m3…mn &#xff1b; 每种砝码对应的数量为 x1,x2,x3...xn 。现在要…...

Qt涂鸦板

Qt版本&#xff1a;Qt6 具体代码&#xff1a; 头文件 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 什么是构造函数 类的构造函数是类的一种特殊的成员函数&#xff0c;它会在每次创建类的新对象时执行。 每次构造的是构造成员变量的初始化值&#xff0c;内存空间等。 构造函数的名称与类的名称是完全相同的&#xff0c;并且不会返回任何类型&#xff0c;也不…...

强化学习中的Double DQN、Dueling DQN和PER DQN算法详解及实战

1. 深度Q网络&#xff08;DQN&#xff09;回顾 DQN通过神经网络近似状态-动作值函数&#xff08;Q函数&#xff09;&#xff0c;在训练过程中使用经验回放&#xff08;Experience Replay&#xff09;和固定目标网络&#xff08;Fixed Target Network&#xff09;来稳定训练过程…...

前端八股文 说一说样式优先级的规则是什么?

标准的回答 CSS样式的优先级应该分成四大类 第一类 !important&#xff1a; &#x1f604;无论引入方式是什么&#xff0c;选择器是什么&#xff0c;它的优先级都是最高的。 第二类 引入方式&#xff1a; &#x1f604;行内样式的优先级要高于嵌入和外链&#xff0c;嵌入和外链…...

洞察国内 AI 绘画行业的璀璨前景

在科技的浪潮中&#xff0c;AI 绘画如同一颗璀璨的新星&#xff0c;正在国内的艺术与技术领域绽放出耀眼的光芒。 近年来&#xff0c;国内 AI 绘画行业发展迅猛&#xff0c;展现出巨大的潜力。随着人工智能技术的不断突破&#xff0c;AI 绘画算法日益精进&#xff0c;能够生成…...

socket编程

文章目录 套接字网路字节序列TCP和UDP套接字 本文章主要介绍Linux下套接字的相关接口&#xff0c;和一些基础知识。 套接字 所有网络通信的行为本质都是进程间进行通信&#xff0c;网络通信也是进程间通信&#xff0c;只不过是不同主机上的两个进程之间的通信。网络通信对于双…...

python自动移除excel文件密码(升级v2版本)

欢迎查看第一版 https://blog.csdn.net/weixin_45631815/article/details/140013476?spm1001.2014.3001.5502 一功能改进 此版本主要改进功能有以下: 直接可以调用函数实现可以尝试多个密码没有加密的文件进行保存,可以按实际业务进行改进.思路来源:java 面向对象设计模式.…...

深入MOJO编程语言的单元测试世界

引言 在软件开发的历程中&#xff0c;单元测试扮演着至关重要的角色。单元测试不仅帮助开发者确保代码的每个部分都按预期工作&#xff0c;而且也是代码质量和维护性的关键保障。本文将引导读者了解如何在MOJO这一假想编程语言中编写单元测试&#xff0c;尽管MOJO并非真实存在…...

Canvas:掌握颜色线条与图像文字设置

想象一下&#xff0c;用几行代码就能创造出如此逼真的图像和动画&#xff0c;仿佛将艺术与科技完美融合&#xff0c;前端开发的Canvas技术正是这个数字化时代中最具魔力的一环&#xff0c;它不仅仅是网页的一部分&#xff0c;更是一个无限创意的画布&#xff0c;一个让你的想象…...

打包导入pyzbar的脚本时的注意事项

目录 前言问题问题的出现解决 总结 本文由Jzwalliser原创&#xff0c;发布在CSDN平台上&#xff0c;遵循CC 4.0 BY-SA协议。 因此&#xff0c;若需转载/引用本文&#xff0c;请注明作者并附原文链接&#xff0c;且禁止删除/修改本段文字。 违者必究&#xff0c;谢谢配合。 个人…...

02-android studio实现下拉列表+单选框+年月日功能

一、下拉列表功能 1.效果图 2.实现过程 1&#xff09;添加组件 <LinearLayoutandroid:layout_width"match_parent"android:layout_height"wrap_content"android:layout_marginLeft"20dp"android:layout_marginRight"20dp"android…...

曹操的五色棋布阵 - 工厂方法模式

定场诗 “兵无常势&#xff0c;水无常形&#xff0c;能因敌变化而取胜者&#xff0c;谓之神。” 在三国的战场上&#xff0c;兵法如棋&#xff0c;布阵如画。曹操的五色棋布阵&#xff0c;不正是今日软件设计中工厂方法模式的绝妙写照吗&#xff1f;让我们从这个神奇的布阵之…...

谷粒商城学习笔记-逆向工程错误记录

文章目录 1&#xff0c;Since Maven 3.8.1 http repositories are blocked.1.1 在maven的settings.xml文件中&#xff0c;新增如下配置&#xff1a;1.2&#xff0c;执行clean命令刷新maven配置 2&#xff0c;internal java compiler error3&#xff0c;启动逆向工程报错&#x…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...