LeetCode 2707. 字符串中的额外字符
一、题目
1、题目描述
给你一个下标从 0 开始的字符串
s和一个单词字典dictionary。你需要将s分割成若干个 互不重叠 的子字符串,每个子字符串都在dictionary中出现过。s中可能会有一些 额外的字符 不在任何子字符串中。请你采取最优策略分割
s,使剩下的字符 最少 。
2、接口描述
class Solution {
public:int minExtraChar(string s, vector<string>& dictionary) {}
};
3、原题链接
2707. 字符串中的额外字符
二、解题报告
1、思路分析
和上周周赛题目类似,也是分割字符串,我们可以用动态规划将问题划分为子问题
定义状态dp[i]为前i个字符最优划分后的最少额外字符,那么有转移方程:
dp[i] = dp[ i -1],将第i个字符作为额外字符
dp[i] = min(dp[i] , dp[j - 1]),其中第j个字符到第i个字符在字典中
最终返回dp[n]即可
进行状态转移,如果暴力计算子串是否在字典中,显然复杂度过高
如果将字典中字符串存入哈希表,那么每次状态转移为n * 2,因为我们要从(i , i)计算到(1 , i)
这里就涉及到查询字符串优化的常用策略,将目标字符串倒序存入字典树,然后倒序查询可以满足一次遍历完成查询,关于字典树见:Trie树/字典树的原理及实现[C/C++]-CSDN博客
2、复杂度
时间复杂度:O(n^2 + ml) 空间复杂度:O(m l * 26)
3、代码详解
class Solution
{
public:struct Node{bool isword = false;unordered_map<char, Node *> child;} root;void insert(string &s){Node *cur = &root;for (int i = s.size() - 1; i >= 0; i--){if (!cur->child.count(s[i]))cur->child[s[i]] = new Node;cur = cur->child[s[i]];}cur->isword = true;}int minExtraChar(string s, vector<string> &dictionary){root.child.clear();for (auto &x : dictionary)insert(x);int n = s.size();vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i <= n; i++){dp[i] = dp[i - 1] + 1;Node *cur = &root;for (int j = i; j >= 1; j--){if (!cur->child.count(s[j - 1]))break;cur = cur->child[s[j - 1]];if (cur->isword)dp[i] = min(dp[i], dp[j - 1]);}}return dp[n];}
};
相关文章:
LeetCode 2707. 字符串中的额外字符
一、题目 1、题目描述 给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串,每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。 请你采取最优策略分割 s ÿ…...
Js进阶31-DOM 操作专题
1. JavaScript 的组成部分: ECMAScript:简称 ES,它是欧洲计算机协会,大概每年的六月中旬定制语法规范。DOM:全称 Document Object Model,即为文档对象类型。BOM:全称 Browser Object Model&…...
Hive之set参数大全-4
F 指定在使用 FETCH 命令提取查询结果时的序列化/反序列化器 hive.fetch.output.serde 是 Hive 的一个配置参数,用于指定在使用 FETCH 命令提取查询结果时的序列化/反序列化器。 以下是一个示例: -- 设置 hive.fetch.output.serde 为 org.apache.had…...
竞赛保研 基于深度学习的人脸识别系统
前言 🔥 优质竞赛项目系列,今天要分享的是 基于深度学习的人脸识别系统 该项目较为新颖,适合作为竞赛课题方向,学长非常推荐! 🧿 更多资料, 项目分享: https://gitee.com/dancheng-senior/…...
9.建造者模式
文章目录 一、介绍二、代码三、实际使用总结 一、介绍 建造者模式旨在将一个复杂对象的构建过程和其表示分离,以便同样的构建过程可以创建不同的表示。这种模式适用于构建对象的算法(构建过程)应该独立于对象的组成部分以及它们的装配方式的…...
简单的MOV转MP4方法
1.下载腾讯的QQ影音播放器, 此播放器为绿色视频播放器, 除了播放下载好的视频外没有臃肿无用功能 官网 QQ影音 百度网盘链接:https://pan.baidu.com/s/1G0kSC-844FtRfqGnIoMALA 提取码:dh4w 2.用QQ影音打开MOV文件 3.右下角打开影音工具箱 , 选择截取…...
YOLOv8改进 | Neck篇 | 利用ASF-YOLO改进特征融合层(适用于分割和目标检测)
一、本文介绍 本文给大家带来的改进机制是ASF-YOLO(发布于2023.12月份的最新机制),其是特别设计用于细胞实例分割。这个模型通过结合空间和尺度特征,提高了在处理细胞图像时的准确性和速度。在实验中,ASF-YOLO在2018年数据科学竞赛数据集上取得了卓越的分割准确性和速度,…...
基于模块自定义扩展字段的后端逻辑实现(一)
目录 一:背景介绍 二:实现过程 三:字段标准化 四:数据存储 五:数据扩展 六:表的设计 一:背景介绍 最近要做一个系统,里面涉及一个模块是使用拖拉拽的形式配置模块使用的字段表…...
力扣:18.四数之和
一、做题链接:18. 四数之和 - 力扣(LeetCode) 二、题目分析 1.做这一道题之前本博主建议先看上一篇《三数之和》 2.题目分析 给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重…...
.netcore 6 ioc注入的三种方式
1、定义接口 public interface MyInterceptorInterface 2、实现接口 public class MyInterceptorImpl : MyInterceptorInterface 在构造中增加以下代码,便于观察 static ConcurrentDictionary<string, string> keyValues new ConcurrentDictionary<s…...
Python轴承故障诊断 (十)基于VMD+CNN-Transfromer的故障分类
目录 1 变分模态分解VMD的Python示例 2 轴承故障数据的预处理 2.1 导入数据 2.2 故障VMD分解可视化 3 基于VMDCNN-Transformer的轴承故障诊断分类 3.1 定义VMD-CNN-Transformer分类网络模型 3.2 设置参数,训练模型 3.3 模型评估 代码、数据如下:…...
【复习】人工智能 第7章 专家系统与机器学习
专家系统就是让机器人当某个领域的专家,但这章专家系统不咋考,主要靠书上没有的机器学习。 一、专家系统的基本组成 二、专家系统与传统程序的比较 (1)编程思想: 传统程序 数据结构 算法 专家系统 知识 推理 &…...
使用 Apache PDFBox 操作PDF文件
简介 Apache PDFBox库是一个开源的Java工具,专门用于处理PDF文档。它允许用户创建全新的PDF文件,编辑现有的PDF文档,以及从PDF文件中提取内容。此外,Apache PDFBox还提供了一些命令行实用工具。 Apache PDFBox提供了创建、渲染、…...
【Python 常用脚本及命令系列 3.2 -- 检测到弹框跳出然后关掉它--脚本实现】
文章目录 简介脚本实现 简介 在Python中,你可以使用第三方库如pyautogui和pygetwindow来检测屏幕上的弹框并关闭它。这些库可以模拟鼠标和键盘操作,也可以获取窗口信息。 首先,需要安装这些库(如果你还没有安装的话)&…...
junit单元测试:使用@ParameterizedTest 和 @CsvSource注解简化单元测试方法
在平常的开发工作中,我们经常需要写单元测试。比如,我们有一个校验接口,可能会返回多种错误信息。我们可以针对这个接口,写多个单元测试方法,然后将其场景覆盖全。那么,怎么才能写一个测试方法,…...
C# winform判断自身程序是否已运行,如果已运行则激活窗体
C# winform判断自身程序是否已运行,如果已运行则激活窗体 using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Reflection; using System.Runtime.InteropServices; using System.Threading; using Syst…...
超维空间M1无人机使用说明书——21、基于opencv的人脸识别
引言:M1型号无人机不仅提供了yolo进行物体识别,也增加了基于opencv的人脸识别功能包,仅需要启动摄像头和识别节点即可 链接: 源码链接 一、一键启动摄像头和人脸识别节点 roslaunch robot_bringup bringup_face_detect.launch无报错&#…...
Redis 持久化——AOF
文章目录 为什么需要AOF?概念持久化查询和设置1. 查询AOF启动状态2. 开启AOF持久化2.1 命令行启动AOF2.2 配置文件启动 AOF 3. 触发持久化3.1 自动触发3.3 手动触发 4. AOF 文件重写4.1 什么是AOF重写?4.2 AOF 重写实现4.3 AOF 重写流程 5. 配置说明6. 数据恢复6.1…...
华为云服务介绍(二)
在 华为云服务介绍(一) 中我们看到华为云提供了一系列的云服务,包括计算、存储、网络、数据库、安全等方面的解决方案。通过灵活的系统架构设计,可以充分利用这些云服务技术,从而更好地满足用户的需求。 本文从系统架构的角度出发,通过充分利用华为云提供的各种云服务技…...
mysql列题
mysql列题 1.查询学过「张三」老师授课的同学的信息2.查询没有学全所有课程的同学的信息3.查询没学过"张三"老师讲授的任一门课程的学生姓名4.查询两门及其以上不及格课程的同学的学号,姓名及其平均成绩5.检索" 01 "课程分数小于 60,…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...
