算法leetcode｜76. 最小覆盖子串（rust重拳出击）

2023-09-04 11:29:35

文章目录

76. 最小覆盖子串：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

样例 1：

输入：
	
	s = "ADOBECODEBANC", t = "ABC"
	
输出：
	
	"BANC"
	
解释：
	
	最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

样例 2：

输入：
	
	s = "a", t = "a"
	
输出：
	
	"a"
	
解释：
	
	整个字符串 s 是最小覆盖子串。

样例 3：

输入: 
	
	s = "a", t = "aa"
	
输出: 
	
	""
	
解释:

	 t 中两个字符 'a' 均应包含在 s 的子串中，
	因此没有符合条件的子字符串，返回空字符串。

提示：

  • m == s.length
  • n == t.length
  • 1 <= m, n <= 105
  • s 和 t 由英文字母组成

进阶：

你能设计一个在 o(m + n) 时间内解决此问题的算法吗？

分析：

  • 面对这道算法题目，二当家的再次陷入了沉思。
  • 直接采用双层循环暴力解决的话，时间复杂度会比较高，恐怕过不了用例，没有去试。
  • 题目并不要求字符的顺序，只要求了每种字符的数量，那首先就想到要做计数。
  • 接下来考虑如何降低时间复杂度，每次循环都从新匹配子串是低效的，要尽可能复用，滑动窗口在这里非常合适，使用双指针，先直接移动右指针找到第一个满足条件的子串，记下长度作为备选结果，接下来移动左指针，当不满足覆盖子串的条件时就继续移动右置针直到满足覆盖子串的条件，并比较子串的长度，取较小的子串长度作为备选结果，重复该操作，直到循环遍历完毕。
  • 如何高效判断遍历的子串已经满足覆盖子串呢？字符计数这时候就要大展拳脚了，先在遍历字符串 s 之前，先对字符串 t 进行一次遍历，做初始化计数，记录下每种字符的个数（题解中这里使用了减法，使用加法也是可以的，只是后面的加减法就要变），在遍历 s 时，移动右指针就是延长了覆盖子串，同时修改计数，这里的加减法计算要和前面初始化的相反，判断计数是否为0，如果变为0则表示，这种字符的个数已经没有差异了，但是我们需要覆盖了 t 中的每一种字符，所以需要判断 26 个字符的个数是不是都够了，如果都够了，就是满足了覆盖子串，接下来就移动左指针，同时修改计数，这里的加减计算要和右指针移动的相反。
  • 当某个字符的计数变为0时，我们需要判断 26 种字符的字符个数是不是都满足了，这里就需要26次循环，是否有更高效的办法呢？我们可以额外增加一个变量记录有差异的字符种类数（记录有差异的字符数也是可以的，但是后面的逻辑会有一点区别，思想大致相同）， 初始化时顺便初始化该变量，在遍历匹配中，每当有字符计数变为0，就修改这个变量，如果这个变量变为0则表示完全覆盖，从而提高效率。
  • 只看文字可能不便理解，建议对照着熟悉的语言的题解一起看，希望可以有助学习理解。

在这里插入图片描述

题解：

rust：

impl Solution {
    pub fn min_window(s: String, t: String) -> String {
        // 少于目标字符串中数量的字符数量
        let mut diff_char_count = 0;
        // 字符计数器
        let mut cnt = vec![0; 128];

        // 初始化
        t.as_bytes().iter().for_each(|&b| {
            // 计数减少
            cnt[b as usize] -= 1;
            if cnt[b as usize] == -1 {
                // 差异字符数增加
                diff_char_count += 1;
            }
        });

        // 覆盖子串结果信息
        let (mut ans_len, mut ans_l) = (usize::MAX, usize::MAX);

        // 开始滑动窗口
        let s_len = s.len();
        let (mut l, mut r) = (0, 0);
        while r < s_len {
            // 计数增加
            cnt[s.as_bytes()[r] as usize] += 1;

            // 向右移动右边界后，可能该字符数量没有差异了
            if cnt[s.as_bytes()[r] as usize] == 0 {
                // 差异字符数减少
                diff_char_count -= 1;
                // 差异字符数减少后可能为0了
                if diff_char_count == 0 {
                    // 向右滑动左边界，直到会有差异，取满足要求的最小串
                    while cnt[s.as_bytes()[l] as usize] > 0 {
                        cnt[s.as_bytes()[l] as usize] -= 1;
                        l += 1;
                    }

                    // 更新结果
                    if r - l + 1 < ans_len {
                        ans_len = r - l + 1;
                        ans_l = l;
                    }

                    // 向右移动左边界，差异字符数增加
                    cnt[s.as_bytes()[l] as usize] -= 1;
                    l += 1;
                    diff_char_count += 1;
                }
            }
            r += 1;
        }

        return if ans_l == usize::MAX {
            "".to_string()
        } else {
            s[ans_l..ans_l + ans_len].to_string()
        }
    }
}

go：

func minWindow(s string, t string) string {
    // 少于目标字符串中数量的字符数量
	diffCharCount := 0
	// 字符计数器
	cnt := make([]int, 128)

	// 初始化
	for _, c := range t {
		// 计数减少
		cnt[c]--
		if cnt[c] == -1 {
			// 差异字符数增加
			diffCharCount++
		}
	}

	// 覆盖子串结果信息
	ansLen, ansL := math.MaxInt32, -1

	// 开始滑动窗口
	sLen := len(s)
	l, r := 0, 0
	for r < sLen {
		// 计数增加
		cnt[s[r]]++

		// 向右移动右边界后，可能该字符数量没有差异了
		if cnt[s[r]] == 0 {
			// 差异字符数减少
			diffCharCount--
			// 差异字符数减少后可能为0了
			if diffCharCount == 0 {
				// 向右滑动左边界，直到会有差异，取满足要求的最小串
				for cnt[s[l]] > 0 {
					cnt[s[l]]--
					l++
				}

				// 更新结果
				if r-l+1 < ansLen {
					ansLen = r - l + 1
					ansL = l
				}

				// 向右移动左边界，差异字符数增加
				cnt[s[l]]--
				l++
				diffCharCount++
			}
		}
		r++
	}

	if ansL == -1 {
		return ""
	} else {
		return s[ansL : ansL+ansLen]
	}
}

c++：

class Solution {
public:
    string minWindow(string s, string t) {
        // 少于目标字符串中数量的字符数量
        int diffCharCount = 0;
        // 字符计数器
        int cnt[128];
        memset(cnt, 0, sizeof(cnt));

        // 初始化
        const int tLen = t.length();
        for (int i = 0; i < tLen; ++i) {
            if (--cnt[t[i]] == -1) {
                // 差异字符数增加
                ++diffCharCount;
            }
        }

        // 覆盖子串结果信息
        int ansLen = INT_MAX, ansL = -1;

        // 开始滑动窗口
        const int sLen = s.length();
        int l = 0, r = -1;
        while (++r < sLen) {
            // 向右移动右边界后，可能该字符数量没有差异了
            if (++cnt[s[r]] == 0) {
                // 差异字符数减少后可能为0了
                if (--diffCharCount == 0) {
                    // 向右滑动左边界，直到会有差异，取满足要求的最小串
                    while (--cnt[s[l++]] >= 0) {
                        // nothing
                    }

                    // 差异字符数增加
                    ++diffCharCount;

                    // 更新结果
                    if (r - l + 2 < ansLen) {
                        ansLen = r - l + 2;
                        ansL = l - 1;
                    }
                }
            }
        }

        return ansL == -1 ? "" : s.substr(ansL, ansLen);
    }
};

python：

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        # 少于目标字符串中数量的字符数量
        diff_char_count = 0
        # 字符计数器
        cnt = collections.defaultdict(int)

        # 初始化
        for c in t:
            # 计数减少
            cnt[c] -= 1
            if cnt[c] == -1:
                # 差异字符数增加
                diff_char_count += 1

        # 覆盖子串结果信息
        ans_len, ans_l = float("inf"), -1

        # 开始滑动窗口
        s_len = len(s)
        l, r = 0, 0
        while r < s_len:
            # 计数增加
            cnt[s[r]] += 1

            # 向右移动右边界后，可能该字符数量没有差异了
            if cnt[s[r]] == 0:
                # 差异字符数减少
                diff_char_count -= 1
                # 差异字符数减少后可能为0了
                if diff_char_count == 0:
                    # 向右滑动左边界，直到会有差异，取满足要求的最小串
                    while cnt[s[l]] > 0:
                        cnt[s[l]] -= 1
                        l += 1

                    # 更新结果
                    if r - l + 1 < ans_len:
                        ans_len = r - l + 1
                        ans_l = l

                    # 向右移动左边界，差异字符数增加
                    cnt[s[l]] -= 1
                    l += 1
                    diff_char_count += 1
            r += 1

        return "" if ans_l == -1 else s[ans_l: ans_l + ans_len]

java：

class Solution {
    public String minWindow(String s, String t) {
        // 少于目标字符串中数量的字符数量
        int diffCharCount = 0;
        // 字符计数器
        final int[] cnt = new int[128];

        // 初始化
        final int tLen = t.length();
        for (int i = 0; i < tLen; ++i) {
            if (--cnt[t.charAt(i)] == -1) {
                // 差异字符数增加
                ++diffCharCount;
            }
        }

        // 覆盖子串结果信息
        int ansLen = Integer.MAX_VALUE, ansL = -1;

        // 开始滑动窗口
        final int sLen = s.length();
        int       l    = 0, r = -1;
        while (++r < sLen) {
            // 向右移动右边界后，可能该字符数量没有差异了
            if (++cnt[s.charAt(r)] == 0) {
                // 差异字符数减少后可能为0了
                if (--diffCharCount == 0) {
                    // 向右滑动左边界，直到会有差异，取满足要求的最小串
                    while (--cnt[s.charAt(l++)] >= 0) {
                        // nothing
                    }

                    // 差异字符数增加
                    ++diffCharCount;

                    // 更新结果
                    if (r - l + 2 < ansLen) {
                        ansLen = r - l + 2;
                        ansL = l - 1;
                    }
                }
            }
        }

        return ansL == -1 ? "" : s.substring(ansL, ansL + ansLen);
    }
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

更多推荐

ARM DAY3

硬件模块与总线连接：各种硬件模块（如GPIO控制器）与CPU（或内核）通过总线进行连接。这个总线负责数据和指令的传输。特殊功能寄存器（SFRs）的角色：每个硬件模块内部都有一组特殊功能寄存器（SFRs）。这些寄存器是硬件模块的一部分，用于存储该模块的当前状态和配置信息。它们在特定的内存地址中有其对应的位置。使用LDR读

华为MTL流程的六个模块初步解析

大家好！昨天华研荟给大家介绍了华为MTL流程的基本概念和发展历程，今天我们来了解下华为MTL流程的六个模块。如昨天所述，华为的MLT流程主要有六个模块：市场洞察、市场管理、联合创新、销售赋能、激发需求、营销质量管理。接下来，我们来了解这六个模块。1.市场洞察在这里指的是通过观察和分析市场动态，了解市场趋势、需求和竞争环

【Android】线程下载资源保证资源到位采用了 OkHttp的三方网络下载 & 文件缓存策略

背景使用SVGA的三方的url播放方式会比较慢，至少延迟3s以上才会出现svga效果，所以改变策略：将线上的svga全部下载到本地进行播放，那么就得将采用网络缓存的方式实现效果。实现那么就得实现以下几点：初次下载缓存判重下载下载的地址就放在这里。这里也是常规的文件路径下载通过上下文类获取即可，如果参数路径没有，就会再构

ETHERCAT转MODBUS TCP/IP协议网关

产品介绍JM-ECT-TCPIP是自主研发的一款EtherCAT从站功能的通讯网关。该产品主要功能是将EtherCAT网络和TCP/IP网络连接起来。本网关连接到EtherCAT总线中做为从站使用，连接到TCP/IP网络中做为服务器或客户端使用。产品参数技术参数u网关做为EtherCAT网络的从站，可以连接倍福、欧姆龙

ASIC-WORLD Verilog（11）过程时序控制

写在前面在自己准备写一些简单的verilog教程之前，参考了许多资料----Asic-World网站的这套verilog教程即是其一。这套教程写得极好，奈何没有中文，在下只好斗胆翻译过来（加了自己的理解）分享给大家。这是网站原文：VerilogTutorial这是系列导航：Verilog教程系列文章导航过程块和时序控制

深入浅出学Verilog--基础语法

1、简介Verilog的语法和C语言非常类似，相对来说还是非常好学的。和C语言一样，Verilog语句也是由一连串的令牌（Token）组成。1个令牌必须由1个或1个以上的字符（character）组成，令牌可以是：注释（Comment）空白符（Whitespace）运算符（Operator）数字（Number）字符串（

新手如何学习RPA，怎么学，从哪下手，学习资源哪里来？

随着人工智能技术的迅速发展，RPA（RoboticProcessAutomation）已经成为企业自动化流程的一个重要工具。越来越多的新手开始学习RPA技术，以便在职场中获得更多的竞争优势。本文将介绍新手如何学习RPA，从哪里开始学习，以及有哪些学习资源可以利用。一、了解RPA基础知识学习RPA的第一步是了解其基础知识

S7通信协议的挑高点

目录1.S7协议之布尔操作2.S7协议之PDU读取3S7协议之多组读取在电气学习的路上，西门子PLC应该是每个人的启蒙PLC，从早期的S7-300/400PLC搭建Profibus-DP网络开始接触，到后来的S7-200SmartPLC，再到现在的S7-1200/1500PLC博途软件。西门子S7协议是非常强大的一个协

面向对象的分析与设计（精品课程）第一章作业

面向对象的分析与设计（精品课程）第一章作业一.单选题（共2题，18分）二.多选题（共3题，27分）三.填空题（共5题，45分）四.简答题（共1题，10分）一.单选题（共2题，18分）(单选题)如果想对一个类的意义进行描述，那么应该采用()。A标记值B规格描述C注释D构造型(单选题)()模型的缺点是缺乏灵活性，特别是无法

Centos 7 部署SVN服务器

一、安装SVN1、安装Subversionsudoyum-yinstallsubversion2、验证是否安装成功（查看svn版本号）svnserve--version二、创建版本库1、先建立目录，目录位置可修改mkdir-p/var/svncd/var/svn2、创建版本库，添加权限svnadmincreate/va

5-3 pytorch中的损失函数

一般来说，监督学习的目标函数由损失函数和正则化项组成。(Objective=Loss+Regularization)Pytorch中的损失函数一般在训练模型时候指定。注意Pytorch中内置的损失函数的参数和tensorflow不同，是y_pred在前，y_true在后，而Tensorflow是y_true在前，y_p

热文推荐
  1. 外包干了2个月，技术退步明显...

    先说一下自己的情况，大专生，19年通过校招进入湖南某软件公司，干了接近4年的功能测试，今年8月份，感觉自己不能够在这样下去了，长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试，已经让我变得不思进取，谈了2年的女朋友也因为我的心态和工资和我分手了。于是，我决定要改变现状，冲击下大厂。刚开始准备

  2. [C/C++]天天酷跑超详细教程-中篇

    个人主页：北·海🎐CSDN新晋作者🎉欢迎👍点赞✍评论⭐收藏✨收录专栏：C/C++🤝希望作者的文章能对你有所帮助，有不足的地方请在评论区留言指正，大家一起学习交流！🤗天天酷跑,一款童年游戏,主要是进行跳跃操作,和躲避障碍物,中篇主要实现人物的下蹲,随机障碍物的生成以及优化main函数里面的sleep(30)一.

  3. Python操作Excel教程（图文教程，超详细）Python xlwings模块详解，

    「作者主页」：士别三日wyx「作者简介」：CSDNtop100、阿里云博客专家、华为云享专家、网络安全领域优质创作者「推荐专栏」：小白零基础《Python入门到精通》xlwings模块详解1、快速入门1、打开Excel2、创建工作簿2.1、使用工作簿2.2、操作工作簿3、创建工作表3.1、使用工作表3.2、操作工作表3

  4. C语言练习题解析：挑战与突破，开启编程新篇章！（3）

    💓博客主页：江池俊的博客⏩收录专栏：C语言刷题专栏👉专栏推荐：✅C语言初阶之路✅C语言进阶之路💻代码仓库：江池俊的代码仓库🎉欢迎大家点赞👍评论📝收藏⭐文章目录🌴选择题🌴编程题📌记负均正📌旋转数组的最小数字🎈前言：本专栏每篇练习将包括5个选择题+2个编程题，将涵盖C语言的不同方面，包括基础语法、数据

  5. Linux：工具(vim,gcc/g++,make/Makefile,yum,git,gdb)

    目录---工具功能1.vim1.1vim的模式1.2vim常见指令2.gcc/g++2.1预备知识2.2gcc的使用3.make,Makefilemake.Makefile的使用4.yum--yum三板斧5.git--git三板斧--Linux下提交代码到远程仓库6.gdb6.1gdb的常用指令学习目标：1.知道这些工

  6. C语言：选择+编程（每日一练）

    目录选择题：题一：题二：题三：题四：题五：编程题：题一：珠玑妙算思路一：题二：两数之和思路一：本人实力有限可能对一些地方解释和理解的不够清晰，可以自己尝试读代码，或者评论区指出错误，望海涵！感谢大佬们的一键三连！感谢大佬们的一键三连！感谢大佬们的一键三连！选择题：题一：1、有以下函数，该函数的功能是（）intfun(c

  7. python-wordcloud词云

    导入模块fromwordcloudimportWordCloudimportjiebaimportimageioimportmatplotlib.pyplotaspltfromPILimportImageGrabimportnumpyasnpwordcloud以空格为分隔符号，来将文本分隔成单词PILpillow模块i

  8. 网络安全（黑客）自学

    前言一、什么是网络安全网络安全可以基于攻击和防御视角来分类，我们经常听到的“红队”、“渗透测试”等就是研究攻击技术，而“蓝队”、“安全运营”、“安全运维”则研究防御技术。无论网络、Web、移动、桌面、云等哪个领域，都有攻与防两面性，例如Web安全技术，既有Web渗透，也有Web防御技术（WAF）。作为一个合格的网络安全

  9. Spring WebSocket 认证与授权：掌控安全通道，迈向巅峰之旅！

    一、需要了解的事项http和WebSocket的安全链和安全配置是完全独立的。SpringAuthenticationProvider根本不参与Websocket身份验证。将要给出的示例中，身份验证不会发生在HTTP协商端点上，因为JavaScriptSTOMP（websocket）库不会随HTTP请求一起发送必要的身