算法求解(C#)-- 寻找包含目标字符串的最短子串算法
1. 引言
在字符串处理中,我们经常需要从一个较长的字符串中找到包含特定目标字符串的最短子串。这个问题在文本搜索、基因序列分析等领域有着广泛的应用。本文将介绍一种高效的算法来解决这个问题。
2. 问题描述
给定一个源字符串 source 和一个目标字符串 target,我们需要找到 source 中包含 target 所有字符的最短子串。如果找不到这样的子串,则返回空字符串。问题来源:炼码 32 · 最小子串覆盖
样例
样例 1:
输入:source = “abc” ;target = “ac”
输出:“abc”
解释:“abc” 是 source 的包含 target 的每一个字符的最短的子串。
样例 2:
输入:source = “adobecodebanc” ;target = “abc”
输出:“banc”
解释:“banc” 是 source 的包含 target 的每一个字符的最短的子串。
样例 3:
输入:source = “abc” ; target = “aa”
输出:“”
解释:没有子串包含两个 ‘a’。
3. 算法思路
为了解决这个问题,我们可以使用滑动窗口(Sliding Window)技术。滑动窗口是一种在数组或字符串上处理问题的有效方法,它可以在一次遍历中解决多个连续子数组或子字符串的问题。
步骤:
1、初始化:
- 创建一个字典 targetCount 来记录 target 中每个字符的出现次数。
- 创建一个字典 windowCount 来记录当前窗口中每个字符的出现次数。
- 初始化两个指针 left 和 right,分别表示窗口的左右边界。
- 初始化变量 matched 来记录当前窗口中已经匹配的 target 中的字符种类数。
- 初始化变量 minStart 和 minLength 来记录最短子串的起始位置和长度。
2、扩展窗口:
- 使用 right 指针向右移动,将字符添加到窗口中。
- 更新 windowCount 和 matched。
3、缩小窗口:
- 当窗口包含了 target 中的所有字符时(即 matched == targetCount.Count),尝试缩小窗口以找到更短的子串。
- 使用 left 指针向左移动,从窗口中移除字符。
- 更新 windowCount 和 matched。
- 如果缩小后的窗口仍然包含 target 中的所有字符,并且长度更短,则更新 minStart 和 minLength。
4、返回结果:
- 根据 minStart 和 minLength 从 source 中提取最短子串并返回。
4. 算法实现
以下是该算法的 C# 实现:
using System;
using System.Collections.Generic;class Program
{static void Main(){string source = "adobecodebanc";string target = "abc";string result = FindShortestSubstringContainingTarget(source, target);Console.WriteLine(result); // Output: "banc"}static string FindShortestSubstringContainingTarget(string source, string target){if (string.IsNullOrEmpty(source) || string.IsNullOrEmpty(target))return string.Empty;Dictionary<char, int> targetCount = new Dictionary<char, int>();foreach (char c in target){targetCount[c] = 0;}foreach (char c in target){targetCount[c]++;}int left = 0, right = 0;int minStart = 0, minLength = int.MaxValue;int matched = 0;Dictionary<char, int> windowCount = new Dictionary<char, int>();while (right < source.Length){char rightChar = source[right];if (targetCount.ContainsKey(rightChar)){if (!windowCount.ContainsKey(rightChar))windowCount[rightChar] = 0;windowCount[rightChar]++;if (windowCount[rightChar] == targetCount[rightChar])matched++;}while (matched == targetCount.Count){if (right - left + 1 < minLength){minStart = left;minLength = right - left + 1;}char leftChar = source[left];if (targetCount.ContainsKey(leftChar)){windowCount[leftChar]--;if (windowCount[leftChar] < targetCount[leftChar])matched--;}left++;}right++;}return minLength == int.MaxValue ? string.Empty : source.Substring(minStart, minLength);}
}
输出结果

5. 示例分析
假设 source = “adobecodebanc”,target = “abc”。
初始时,left = 0,right = 0,matched = 0,minStart = 0,minLength = int.MaxValue。
随着 right 的移动,窗口逐渐扩展,直到包含 target 中的所有字符。
当窗口包含 abc 时(例如,当 right 指向 c 时),开始缩小窗口。
在缩小窗口的过程中,找到包含 abc 的最短子串 “banc”。
6. 结论
本文介绍了一种使用滑动窗口技术来寻找包含目标字符串的最短子串的算法。该算法通过维护一个窗口来动态地包含和排除字符,从而在一次遍历中找到了最短子串。这种方法不仅高效,而且易于理解和实现。
相关文章:
算法求解(C#)-- 寻找包含目标字符串的最短子串算法
1. 引言 在字符串处理中,我们经常需要从一个较长的字符串中找到包含特定目标字符串的最短子串。这个问题在文本搜索、基因序列分析等领域有着广泛的应用。本文将介绍一种高效的算法来解决这个问题。 2. 问题描述 给定一个源字符串 source 和一个目标字符串 targe…...
AscendC从入门到精通系列(二)基于Kernel直调开发AscendC算子
本次主要讨论下AscendC算子的开发流程,基于Kernel直调工程的算子开发。 1 AscendC算子开发的基本流程 使用Ascend C完成Add算子核函数开发; 使用ICPU_RUN_KF CPU调测宏完成算子核函数CPU侧运行验证; 使用<<<>>>内核调用符…...
DAO模式的理解
目录 DAO模式 含义 DAO模式 的理解 分层思维 分层含义 分层目的 dao层 dao包(对接的是操作数据库的接口) dao包下lmpl 包(dao包中接口的实现类) 补充 1 你创建的实体类需要和数据库中建的表一一对应。 总结 DAO模式 含义…...
使用GitHub Actions实现CI/CD流程
💓 博客主页:瑕疵的CSDN主页 📝 Gitee主页:瑕疵的gitee主页 ⏩ 文章专栏:《热点资讯》 使用GitHub Actions实现CI/CD流程 GitHub Actions 简介 创建仓库 配置工作流 示例工作流文件 触发和运行工作流 部署应用 最佳实…...
机器人助力Bridge Champ游戏:1.4.2版本如何提升玩家体验
在Bridge Champ游戏中,机器人扮演着桥牌游戏的“无名英雄”角色,默默地提升玩家体验。凭借智能化的设计,这些机器人不仅能够陪练,也大大提升了比赛的流畅度与趣味性。 Bridge Champ是什么 Bridge Champ是一个基于Ignis公链的在线…...
滑动窗口(单调队列维护窗口)-acwing
题目: 154. 滑动窗口 - AcWing题库 代码(删除队列窗口多余的>单调队列) 判断最值是否滑出窗口可以放在 入队的后面。 但是,判断,准备入队元素比前面小,要从队尾出队,放在入队前。 总之&a…...
ALB搭建
ALB: 多级分发、消除单点故障提升应用系统的可用性(健康检查)。 海量微服务间的高效API通信。 自带DDoS防护,集成Web应用防火墙 配置: 1.创建ECS实例 2.搭建应用 此处安装的LNMP 3.创建应用型负载均衡ALB实例 需要创建服务关联角…...
c# 动态lambda实现二级过滤(支持多种参数类型和模糊查询)
效果 调用方法 实体类(可以根据需求更换) public class ToolStr50 {public bool isSelected { get; set; }public string toolStr1 { get; set; }public string toolStr2 { get; set; }public string toolStr3 { get; set; }public string toolStr4 { …...
第J5周:DenseNet+SE-Net实战
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 任务: ●1. 在DenseNet系列算法中插入SE-Net通道注意力机制,并完成猴痘病识别 ●2. 改进思路是否可以迁移到其他地方呢 ●3. 测试集acc…...
Intern大模型训练营(五):书生大模型全链路开源体系笔记
观看视频,可以比较详细地了解到书生大模型全链路开源体系。 其中有几个印象比较深的点: 这张图讲述了书生浦语大模型开源的发展史,同时与主流的llama和Chatgpt模型进行比较,可以看出在参数上,InterLM在努力追赶甚至超…...
聚观早报 | 比亚迪腾势D9登陆泰国;苹果 iOS 18.2 将发布
聚观早报每日整理最值得关注的行业重点事件,帮助大家及时了解最新行业动态,每日读报,就读聚观365资讯简报。 整理丨Cutie 11月5日消息 比亚迪腾势D9登陆泰国 苹果 iOS 18.2 将发布 真我GT7 Pro防尘防水细节 小米15 Ultra最快明年登场 …...
微信小程序开发,诗词鉴赏app,诗词搜索实现(三)
微信小程序开发,诗词鉴赏app(一): https://blog.csdn.net/jky_yihuangxing/article/details/143501681微信小程序开发,诗词鉴赏app,诗词推荐实现(二):https://blog.csdn.net/jky_yih…...
Kotlin 协程使用及其详解
Kotlin协程,好用,但是上限挺高的,我一直感觉自己就处于会用,知其然不知其所以然的地步。 做点小总结,比较浅显。后面自己再继续补充吧。 一、什么是协程? Kotlin 协程是一种轻量级的并发编程方式&#x…...
计算机组成原理--三章四章
这里写目录标题 第三章:存储系统3.1 存储系统基本概念引入存储器的层次结构简介产品 存储器的分类按层次分类按照介质分类按照存取方式分类按照信息的可更改性按照信息的可保护性 存储器的性能指标存储容量单位成本存储速度 总结 3.2主存储器的基本组成半导体元器件…...
单片机工程使用链接优化-flto找不到定义_链接静态库
IDE: CLion HOST: Windows 11 MinGW:x86_64-14.2.0-release-posix-seh-ucrt-rt_v12-rev0 GCC: arm-gnu-toolchain-13.3.rel1-mingw-w64-i686-arm-none-eabi 示例工程:https://github.com/ichliebedich-DaCapo/STM…...
UniTask/Unity的PlayerLoopTiming触发顺序
开始尝试在项目中使用UniTask,发现其中的UniTask.Yield确实很好用,还可以传入PlayerLoopTiming来更细致的调整代码时机,不过平常在Mono中接触的只有Awake,Start,Update等常用Timing,其他的就没怎么接触了&a…...
【报错记录】Steam迁移(移动)游戏报:移动以下应用的内容失败:XXX: 磁盘写入错误
前言 由于黑神话悟空,导致我的2TB的SSD系统盘快满了,我又买了一块4TB的SSD用来存放游戏,我就打算把之前C盘里的游戏移动到D盘,结果Steam移动游戏居然报错了,报的还是“磁盘写入错误”,如下图所示ÿ…...
C 语言学习-04【结构化程序设计】
1、单分支结构语句 用单分支结构进行奇偶判断: #include <stdio.h>int main() {int num;printf("Please enter an integer: ");scanf("%d", &num);if (num % 2 ! 0) {printf("%d is odd! \n", num);}if (num % 2 0) {prin…...
机器视觉:轮廓匹配算法原理
轮廓匹配的模板变量主要包括模板图像(Template)和待检测图像(Source Image) 在轮廓匹配中,模板变量主要包括一下几个关键部分: 模板图像(Template):这是进行匹配的…...
动力商城-02 环境搭建
1.父工程必须满足:1.1删除src目录 1.2pom 2.依赖继承 //里面的依赖,后代无条件继承<dependencies></dependencies>//里面的依赖,后代想要继承,得自己声明需要使用,可以不写版本号,自动继承&l…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
