首页 > 编程语言 >算法求解(C#)-- 寻找包含目标字符串的最短子串算法

算法求解(C#)-- 寻找包含目标字符串的最短子串算法

时间:2024-11-09 16:44:08浏览次数:7  
标签:子串 right 窗口 target source C# windowCount -- 算法

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. 结论

本文介绍了一种使用滑动窗口技术来寻找包含目标字符串的最短子串的算法。该算法通过维护一个窗口来动态地包含和排除字符,从而在一次遍历中找到了最短子串。这种方法不仅高效,而且易于理解和实现。

标签:子串,right,窗口,target,source,C#,windowCount,--,算法
From: https://blog.csdn.net/qq_21419015/article/details/143645987

相关文章

  • WPF 集合操作进阶:提取特定字段、转换 ObservableCollection 和过滤数据
    文章目录1.引言2.从List<T>提取特定字段3.将List<T>转换为observableCollection<T>4.过滤List<T>集合5.总结6.完整示例代码1.引言在C#开发中,集合操作是非常常见的任务,特别是在数据处理和用户界面设计中。本文将介绍如何从List<T>中提取......
  • HTML_CSS笔记
    软件准备软件的安装常用的编辑器(3)VscodeH-buildersublime汉化插件chinese编码提示HtmlCss浏览器运行插件openinbrowser/openindefaultbrowser服务端运行插件liveserver编辑器的设置自动保存autosave字体大小font-size折......
  • DE-9IM 空间关系模型
    参考博客:空间拓扑关系描述:9交叉模型(DE-9IM)|会飞的大象DE-9IM空间关系模型-乌合之众-博客园DE-9IM空间关系模型与BoostGeometryLib-SuperVan-博客园简述DE-9IM是DimensionallyExtended9-IntersectionModel的缩写,它是Egenhofer在《pointsettopologic......
  • BUU BRUTE 1 wp
    BUUBRUTE1引子·burpsuite实战指南尝试一下发现用户名和密码是分离的,手动输入常用用户名,发现为admin,得到提示密码是四位数字。之后用bpIntruder尝试爆破,设置payload需要注意的是如果请求间隔太短会报429错误,fix一下请求间隔时间或者设置自动控制429即可。在......
  • 代码随想录算法训练营第十七天| 654.最大二叉树 , 617.合并二叉树 , 700.二叉搜索树中的
    654.最大二叉树文章链接:https://programmercarl.com/0654.最大二叉树.html题目链接:https://leetcode.cn/problems/maximum-binary-tree/description/classSolution{public:TreeNode*traversal(vector<int>&nums,intleft,intright){if(left>=right)ret......
  • python之判断语句
    一、if语句(1)单分支:格式:if判断条件执行语句块1else:执行语句块2备注:判断条件if中可以使用比较运算符,<,!=,,>=,<=案例1:a=10ifa!=10:print("你中奖了")else:print("谢谢惠顾")2、if语句多分支if判断条件1:执行语句1;elif判断条件2:执行语句2:elif判断条件......
  • 11.9 javaweb学习 day2 基础标签&样式
    网页响应流程浏览器前端服务器后端服务器数据库1.浏览器请求前端2.前端响应浏览器3.浏览器请求后端4.后端请求数据库5.数据库响应后端6.后端响应浏览器网页的组成1.网页的文字,图片,音频,视频,超链接什么的,本质是前端代码2.前端代码通过浏览器的转化......
  • 项目流程
    项目初始[不要有多余的php代码[除了在phpEnv下载的]]1.在phpEnv中网站在www根目录下增加网站![注意端口的设置不要冲突]·image2.在项目中加载thinkphp:[选择未安装,-安装则在phpEnv打开对应文件删除]①在终端输入composer,判断是否已安装,未安装在phpEnv安装②未安装在phpEnv......
  • rocky linux 重启网卡命令
    通用的命令 ifdown ens33关闭网卡名叫ens33的网卡ifup ens33  开启网卡名叫ens33的网卡查看IP地址ip aCentos8和RockyLinux 管理网卡新命令 nmcli connection和c都可以 1、重载网卡,重启网卡之前一定要重新载入一下配置文件,不然不能......
  • 目标1.id管理系统
    1.功能:每一个玩家进入时按顺序分配id2.实现数字计分板:,每实现一次功能+1id计分板,对新进入的玩家将数字计分板的值赋给id计分板,后对其授予(已经给予id)的标签实现:scoreboardobjectivesaddiddummy玩家编号//创建id计分板scoreboardobjectivesaddnumberdummy计数器//......