C++算法:包含三个字符串的最短字符串
涉及知识点
有序集合 字符串
题目
给你三个字符串 a ,b 和 c , 你的任务是找到长度 最短 的字符串,且这三个字符串都是它的 子字符串 。
如果有多个这样的字符串,请你返回 字典序最小 的一个。
请你返回满足题目要求的字符串。
注意:
两个长度相同的字符串 a 和 b ,如果在第一个不相同的字符处,a 的字母在字母表中比 b 的字母 靠前 ,那么字符串 a 比字符串 b 字典序小 。
子字符串 是一个字符串中一段连续的字符序列。
示例 1:
输入:a = “abc”, b = “bca”, c = “aaa”
输出:“aaabca”
解释:字符串 “aaabca” 包含所有三个字符串:a = ans[2…4] ,b = ans[3…5] ,c = ans[0…2] 。结果字符串的长度至少为 6 ,且"aaabca" 是字典序最小的一个。
示例 2:
输入:a = “ab”, b = “ba”, c = “aba”
输出:“aba”
解释:字符串 “aba” 包含所有三个字符串:a = ans[0…1] ,b = ans[1…2] ,c = ans[0…2] 。由于 c 的长度为 3 ,结果字符串的长度至少为 3 。“aba” 是字典序最小的一个。
参数范围:
1 <= a.length, b.length, c.length <= 100
a ,b ,c 只包含小写英文字母。
分析
合并两个字符串
假定a在前,b在后。有如下两种情况。
| a包括b | a=“ab”,b=“a”,合并后为"ab" |
| a的后缀和b的前缀相同,以下简称公共后前缀 | a=“ab”,b=“bc”,合并后"abc" |
分两部
| 第一步 | 第二步 |
|---|---|
| ab | abc |
| ab | c(ab) |
| ac | acb |
| ac | b(ac) |
| ba | bac |
| ba | c(ba) |
| bc | bca |
| bc | a(bc) |
| ca | cab |
| ca | b(ca) |
| cb | cba |
| cb | a(cb) |
| 共12种情况 |
abc和a(bc)相同
abc和a(bc)相比,效果相同或更好,所以无需考虑a(bc)等。
| bc是第一种情况 | abc就是ab,a(bc)也是 |
| ab是第一种情况 | 这种情况不符合,abc=ac a(bc)等于a(xc),如果xc是的前缀是a的后缀,且比x长,那c也是后缀,两者节省的长度相同。如果xc的前缀不是a的后缀,则c的前缀有可能是a的后缀,这种情况下:abc优于a(bc)。 |
| ab和bc都是第二种情况 | abc = a减去ab公共后前缀+b+c减去bc公共后前缀 a(bc)也是 |
变量函数解释
| m_setStrs | 记录备选答案,自动根据长度和字典序排序 |
| next_permutation | 下一个顺序,初始要排序,使得初始最小序 |
代码
class Solution {
public:string minimumString(string a, string b, string c) {vector<string> strs = { a,b,c };sort(strs.begin(), strs.end());do{string tmp = Union(strs[0], strs[1]);tmp = Union(tmp, strs[2]);m_setStrs.emplace(tmp.length(), tmp);} while (next_permutation(strs.begin(), strs.end()));return m_setStrs.begin()->second;}string Union(const string& a, const string& b){if (-1 != a.find(b)){return a;}int len = min(a.length(), b.length());int i = len;for (; i > 0; i--){if (a.substr(a.length() - i) == b.substr(0, i)){break;}}return a.substr(0, a.length() - i) + b;}std::set<std::pair<int, string>> m_setStrs;
};
旧版代码
class Solution {
public:
string minimumString(string a, string b, string c) {
vector strs = { a,b,c };
sort(strs.begin(), strs.end());
if (-1 != strs[1].find(strs[0]))
{
strs[0] = “”;
}
if (-1 != strs[2].find(strs[1]))
{
strs[1] = “”;
}
do
{
Union(strs[0], strs[1], strs[2]);
} while (next_permutation(strs.begin(), strs.end()));
return m_setStrs.begin()->second;
}
void Union(const string& a, const string& b, const string& c)
{
string tmp = Union(a, b);
tmp = Union(tmp, c);
m_setStrs.emplace(tmp.length(), tmp);
}
string Union(const string& a, const string& b)
{
if (-1 != a.find(b))
{
return a;
}
int len = min(a.length(), b.length());
int i = len;
for (; i > 0; i–)
{
if (a.substr(a.length()-i)== b.substr(0,i))
{
break;
}
}
return a.substr(0, a.length() - i) + b;
}
std::set<std::pair<int, string>> m_setStrs;
};
旧版代码二
class Solution {
public:
string minimumString(string a, string b, string c) {
Union(a, b, c);
Union(a, c, b);
Union(b, a, c);
Union(b, c, a);
Union(c, a, b);
Union(c, b, a);
return m_setStrs.begin()->second;
}
void Union(const string& a, const string& b,const string& c)
{
string tmp = Union(a, b);
tmp = Union(tmp, c);
m_setStrs.emplace(tmp.length(),tmp);
tmp = Union(b, c);
tmp = Union(a, tmp);
m_setStrs.emplace(tmp.length(), tmp);
}
string Union(const string& a, const string& b)
{
if (-1 != a.find(b))
{
return a;
}
int len = min(a.length(), b.length());
int i = len;
for (; i > 0; i–)
{
if (Same(a, b, i))
{
break;
}
}
return a.substr(0, a.length() - i) + b;
}
bool Same(const string& a, const string& b, int len)
{
for (int i = 0; i < len; i++)
{
if (a[a.length() - len + i] != b[i])
{
return false;
}
}
return true;
}
std::set<std::pair<int,string>> m_setStrs;
};
2023年8月份代码
class Solution {
public:
string minimumString(string a, string b, string c) {
Cat(a, b, c);
Cat(a, c, b);
Cat(b, a, c);
Cat(b, c, a);
Cat(c, a, b);
Cat(c, b, a);
string strRet = *m_setCan.begin();
for (const auto& it : m_setCan )
{
if (it.length() < strRet.length())
{
strRet = it;
}
}
return strRet;
}
void Cat(string a, string b, string c)
{
std::set setCan;
Cat(setCan, a, b);
for (const auto& it : setCan)
{
Cat(m_setCan, it, c);
}
}
void Cat(std::set& setCan,string a, string b)
{
int i = min(a.length(), b.length());
for (; i >= 1 ; i–)
{
const auto tmp1 = a.substr(a.length() - i);
const auto tmp2 = b.substr(0, i);
if (tmp1 == tmp2)
{
setCan.emplace(a + b.substr(i));
}
}
setCan.emplace(a + b);
if (-1 != a.find(b))
{
setCan.emplace(a);
}
}
std::set m_setCan;
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法,请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 洒家想对大家说的话 |
|---|
| 闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 墨家名称的来源:有所得以墨记之。 |
| 如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:
VS2022 C++17

相关文章:
C++算法:包含三个字符串的最短字符串
涉及知识点 有序集合 字符串 题目 给你三个字符串 a ,b 和 c , 你的任务是找到长度 最短 的字符串,且这三个字符串都是它的 子字符串 。 如果有多个这样的字符串,请你返回 字典序最小 的一个。 请你返回满足题目要求的字符串。…...
华为开源carbondata中的使用问题处理
carbondata中的使用问题处理 Q:什么是不良记录? A:由于数据类型不兼容而无法加载到CarbonData中的记录或为空或具有不兼容格式的记录被归类为不良记录。 Q:CarbonData中的不良记录存储在哪里? A:不良记录…...
AI:76-基于机器学习的智能城市交通管理
🚀 本文选自专栏:AI领域专栏 从基础到实践,深入了解算法、案例和最新趋势。无论你是初学者还是经验丰富的数据科学家,通过案例和项目实践,掌握核心概念和实用技能。每篇案例都包含代码实例,详细讲解供大家学习。 📌📌📌在这个漫长的过程,中途遇到了不少问题,但是…...
区块链游戏,游戏开发
区块链游戏是一种基于区块链技术的新兴游戏类型,它具有去中心化、安全性高、透明度高、可追溯等特点。与传统的游戏开发相比,区块链游戏开发需要更多的技术和知识储备,同时也需要更加注重游戏本身的玩法和用户体验。 在区块链游戏中ÿ…...
单片机程序无法下载?
原因一:电源问题 电源可能是导致STM32微控制器无法下载程序的一个常见原因。确保电源稳定对于正常运行和下载程序至关重要。以下是一些电源问题: 1. 电源电压不足:如果STM32微控制器没有足够的电压供应,它可能无法正常工作或下载程…...
【数据库】【sql】如何用SQL实现跨行计算
【背景】 这里的跨行计算不是指整体聚合类的函数比如SUM等的功能,而是指递归算法。 比如我接到有需求,有一个结果字段需要是目前所有行该字段的和,这是属于递归类的算法,SQL中如何实现呢? 【方法】 可以使用窗口函数…...
Oracle(概念含安装)
Oracle是一种关系数据库管理系统(RDBMS),是由美国甲骨文公司(Oracle Corporation)开发的。它是一个客户端/服务器系统,可以在各种操作系统上运行,包括Windows、Linux和Unix等。Oracle的设计重点…...
P6入门:项目初始化4-项目详情之预算日志及汇总Budget
前言 使用项目详细信息查看和编辑有关所选项目的详细信息,在项目创建完成后,初始化项目是一项非常重要的工作,涉及需要设置的内容包括项目名,ID,责任人,日历,预算,资金,分类码等等&…...
CSS 中BFC是什么?
在CSS中,BFC(块级格式化上下文)是一个重要的概念,它对于理解和解决布局中的一些问题非常有帮助。本文将深入探讨BFC是什么,以及如何使用代码来详细解释BFC的概念和应用。 引言 在Web开发中,页面布局是一个…...
uniapp的几种跳转方式
1、UniApp是一个跨平台的应用开发框架,可以用于开发同时支持多个平台(如iOS、Android、H5等)的应用程序。在UniApp中,有多种方式可以实现页面之间的跳转。以下是其中一些常用的跳转方式: 页面跳转(navigat…...
【MySQL】初识数据库
目录 1.概念2.基本使用显示当前的数据库列表创建数据库使用数据库创建表向表中插入数据查看创建的表中的数据 3.SQL的分类4.存储引擎 1.概念 MySQL本质是基于C(mysql)S(mysqld)模式的一种网络服务。 mysqld:它是数据库的服务器端(这是一个守护进程&…...
计算机网络(一)
一、什么是计算机网络、计算机协议? 计算机网络就是由计算机作为收发端,不同计算机相互连接的网络,包括互联网(Internet),公司或者家用网络(intranet)等等;其中Internet…...
英语经典名句,柯桥成人英语培训
.Every man has his price.--“天生我材必有用必有用”. Well begun is half done.--“好的开端是成功的一半”. Good wine needs no bush.--“好酒不怕巷子深”. Little stone fell great oaks.--“滴水穿石” Man is good but old is hot.--"人是实的好,…...
@JSONField或@JsonProperty注解使用
一、需求 使用JSONField或JsonProperty注解,来解决bean与json字段不一致问题,或者字段定义不符合前端所需要的标准,最近在项目中发现实体类属性中,同时使用了JSONField和JsonProperty注解,用于重新声明属性key。有时候…...
高效简洁的文档翻译网站
一款简单而强大的文档翻译网站 一款文字/文件翻译的网站,支持多个领域的翻译,支持常见的语言翻译(韩/日/法/英/俄/德…),最大百分比的保持原文排版(及个别除外基本100%还原)。 新用户注册就有100页的免费额度,每月系统还会随机赠送翻译额度,…...
SpringBoot自动装配定义先后顺序失效原因极其解析
SpringBoot自动装配定义先后顺序失效原因极其解析 1、场景分析1.1、问题总结 2、使用AutoConfigureBefore、AutoConfigureAfter和AutoConfigureOrder注解指定加载顺序2.2、AutoConfigureXX注解失效原因总结 3、使用静态内部装配类提升加载顺序4、bean加载顺序规则 1、场景分析 …...
API 集成测试工具Hitchhiker 0.1.1 正式发布
Hitchhiker 是一款开源的 Restful Api 集成测试工具,你可以在轻松部署到本地,和你的 team 成员一起管理 Api。 能做什么 * Team 协作开发 Api * Api 历史修改记录及支持 diff 展示 * 支持多环境变量及运行时变量 * 支持 Schedule 及批量 run * 不同…...
idea无法下载源码-Cannot download sources
问题: 解决方案:...
docker搭建mysql主从复制
1. 基础环境 环境 名称描述CentOS 7.6Linux操作系统版本docker 20.10.5docker版本mysql 8.0.29mysql镜像版本 节点 节点名称读写/主从地址端口master读节点/主节点192.168.1.6:3306slave1写节点/从节点192.168.1.6:3307slave2写节点/从节点192.168.1.6:3308 2. 主节点 使…...
在MacBook上实现免费的PDF文件编辑
之前我想对PDF文件进行简单处理(比如删页面、添空白页、调整页面顺序),要么是开wps会员【花钱贵】,下载(盗版)Adobe Acrobat【macOS不好下载】,要么用福昕阅览器登陆学生账号(学校买…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
