C++实现LeetCode(76.最小窗口子串)

[LeetCode] 76. Minimum Window Substring 最小窗口子串

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

这道题给了我们一个原字符串S,还有一个目标字符串T,让在S中找到一个最短的子串,使得其包含了T中的所有的字母,并且限制了时间复杂度为 O(n)。这道题的要求是要在 O(n) 的时间度里实现找到这个最小窗口字串,暴力搜索 Brute Force 肯定是不能用的,因为遍历所有的子串的时间复杂度是平方级的。那么来想一下,时间复杂度卡的这么严,说明必须在一次遍历中完成任务,当然遍历若干次也是 O(n),但不一定有这个必要,尝试就一次遍历拿下!那么再来想,既然要包含T中所有的字母,那么对于T中的每个字母,肯定要快速查找是否在子串中,既然总时间都卡在了 O(n),肯定不想在这里还浪费时间,就用空间换时间(也就算法题中可以这么干了,七老八十的富翁就算用大别野也换不来时间啊。依依东望,望的就是时间呐 T.T),使用 HashMap,建立T中每个字母与其出现次数之间的映射,那么你可能会有疑问,为啥不用 HashSet 呢,别急,讲到后面你就知道用 HashMap 有多妙,简直妙不可言~

目前在脑子一片浆糊的情况下,我们还是从简单的例子来分析吧,题目例子中的S有点长,换个短的 S = "ADBANC",T = "ABC",那么肉眼遍历一遍S呗,首先第一个是A,嗯很好,T中有,第二个是D,T中没有,不理它,第三个是B,嗯很好,T中有,第四个又是A,多了一个,礼多人不怪嘛,收下啦,第五个是N,一边凉快去,第六个终于是C了,那么貌似好像需要整个S串,其实不然,注意之前有多一个A,就算去掉第一个A,也没事,因为第四个A可以代替之,第二个D也可以去掉,因为不在T串中,第三个B就不能再去掉了,不然就没有B了。所以最终的答案就"BANC"了。通过上面的描述,你有没有发现一个有趣的现象,先扩展,再收缩,就好像一个窗口一样,先扩大右边界,然后再收缩左边界,上面的例子中右边界无法扩大了后才开始收缩左边界,实际上对于复杂的例子,有可能是扩大右边界,然后缩小一下左边界,然后再扩大右边界等等。这就很像一个不停滑动的窗口了,这就是大名鼎鼎的滑动窗口 Sliding Window 了,简直是神器啊,能解很多子串,子数组,子序列等等的问题,是必须要熟练掌握的啊!

下面来考虑用代码来实现,先来回答一下前面埋下的伏笔,为啥要用 HashMap,而不是 HashSet,现在应该很显而易见了吧,因为要统计T串中字母的个数,而不是仅仅看某个字母是否在T串中出现。统计好T串中字母的个数了之后,开始遍历S串,对于S中的每个遍历到的字母,都在 HashMap 中的映射值减1,如果减1后的映射值仍大于等于0,说明当前遍历到的字母是T串中的字母,使用一个计数器 cnt,使其自增1。当 cnt 和T串字母个数相等时,说明此时的窗口已经包含了T串中的所有字母,此时更新一个 minLen 和结果 res,这里的 minLen 是一个全局变量,用来记录出现过的包含T串所有字母的最短的子串的长度,结果 res 就是这个最短的子串。然后开始收缩左边界,由于遍历的时候,对映射值减了1,所以此时去除字母的时候,就要把减去的1加回来,此时如果加1后的值大于0了,说明此时少了一个T中的字母,那么 cnt 值就要减1了,然后移动左边界 left。你可能会疑问,对于不在T串中的字母的映射值也这么加呀减呀的,真的大丈夫(带胶布)吗?其实没啥事,因为对于不在T串中的字母,减1后,变-1,cnt 不会增加,之后收缩左边界的时候,映射值加1后为0,cnt 也不会减少,所以并没有什么影响啦,下面是具体的步骤啦:

- 先扫描一遍T,把对应的字符及其出现的次数存到 HashMap 中。

- 然后开始遍历S,就把遍历到的字母对应的 HashMap 中的 value 减一,如果减1后仍大于等于0,cnt 自增1。

- 如果 cnt 等于T串长度时,开始循环,纪录一个字串并更新最小字串值。然后将子窗口的左边界向右移,如果某个移除掉的字母是T串中不可缺少的字母,那么 cnt 自减1,表示此时T串并没有完全匹配。

解法一:

class Solution {
public:
    string minWindow(string s, string t) {
        string res = "";
        unordered_map<char, int> letterCnt;
        int left = 0, cnt = 0, minLen = INT_MAX;
        for (char c : t) ++letterCnt[c];
        for (int i = 0; i < s.size(); ++i) {
            if (--letterCnt[s[i]] >= 0) ++cnt;
            while (cnt == t.size()) {
                if (minLen > i - left + 1) {
                    minLen = i - left + 1;
                    res = s.substr(left, minLen);
                }
                if (++letterCnt[s[left]] > 0) --cnt;
                ++left;
            }
        }
        return res;
    }
};

这道题也可以不用 HashMap,直接用个 int 的数组来代替,因为 ASCII 只有256个字符,所以用个大小为 256 的 int 数组即可代替 HashMap,但由于一般输入字母串的字符只有 128 个,所以也可以只用 128,其余部分的思路完全相同,虽然只改了一个数据结构,但是运行速度提高了一倍,说明数组还是比 HashMap 快啊。还可以进一步的优化,没有必要每次都计算子串,只要有了起始位置和长度,就能唯一的确定一个子串。这里使用一个全局变量 minLeft 来记录最终结果子串的起始位置,初始化为 -1,最终配合上 minLen,就可以得到最终结果了。注意在返回的时候要检测一下若 minLeft 仍为初始值 -1,需返回空串,参见代码如下:

解法二:

class Solution {
public:
    string minWindow(string s, string t) {
        vector<int> letterCnt(128, 0);
        int left = 0, cnt = 0, minLeft = -1, minLen = INT_MAX;
        for (char c : t) ++letterCnt[c];
        for (int i = 0; i < s.size(); ++i) {
            if (--letterCnt[s[i]] >= 0) ++cnt;
            while (cnt == t.size()) {
                if (minLen > i - left + 1) {
                    minLen = i - left + 1;
                    minLeft = left;
                }
                if (++letterCnt[s[left]] > 0) --cnt;
                ++left;
            }
        }
        return minLeft == -1 ? "" : s.substr(minLeft, minLen);
    }
};

到此这篇关于C++实现LeetCode(76.最小窗口子串)的文章就介绍到这了,更多相关C++实现最小窗口子串内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C++实现LeetCode(66.加一运算)

    [LeetCode] 66. Plus One 加一运算 Given a non-empty array of decimal digits representing a non-negative integer, increment one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the a

  • C++实现LeetCode(72.编辑距离)

    [LeetCode] 72. Edit Distance 编辑距离 Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word: Insert a character Delete a character Replace a char

  • C++实现LeetCode(68.文本左右对齐)

    [LeetCode] 68.Text Justification 文本左右对齐 Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified. You should pack your words in a greedy approach; that i

  • C++实现LeetCode( 69.求平方根)

    [LeetCode] 69. Sqrt(x) 求平方根 Implement int sqrt(int x). Compute and return the square root of x, where x is guaranteed to be a non-negative integer. Since the return type is an integer, the decimal digits are truncated and only the integer part of the

  • C++实现LeetCode(71.简化路径)

    [LeetCode] 71.Simplify Path 简化路径 Given an absolute path for a file (Unix-style), simplify it. For example, path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" click to show corner cases. Corner Cases

  • C++实现LeetCode(73.矩阵赋零)

    [LeetCode] 73.Set Matrix Zeroes 矩阵赋零 Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. Follow up: Did you use extra space? A straight forward solution using O(mn) space is probably

  • C++实现LeetCode(67.二进制数相加)

    [LeetCode] 67. Add Binary 二进制数相加 Given two binary strings a and b, return their sum as a binary string. Example 1: Input: a = "11", b = "1" Output: "100" Example 2: Input: a = "1010", b = "1011" Output: &q

  • C++实现LeetCode(76.最小窗口子串)

    [LeetCode] 76. Minimum Window Substring 最小窗口子串 Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). Example: Input: S = "ADOBECODEBANC", T = "ABC" Output: "BA

  • C++实现LeetCode(64.最小路径和)

    [LeetCode] 64. Minimum Path Sum 最小路径和 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in t

  • C++实现LeetCode(155.最小栈)

    [LeetCode] 155. Min Stack 最小栈 Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. push(x) -- Push element x onto stack. pop() -- Removes the element on top of the stack. top() -- Get the top element. getM

  • c语言输出字符串中最大对称子串长度的3种解决方案

    问题描述: 输入一个字符串,输出该字符串中最大对称子串的长度.例如输入字符串:"avvbeeb",该字符串中最长的子字符串是"beeb",长度为4,因而输出为4. 解决方法:中序遍历 一,全遍历的方法: 1.全遍历的方法,复杂度O(n3); 2.遍历原字符串的所有子串,然后判断每个子串是否对称: 实现方法是:我们让一个指针i从头至尾遍历,我们用另一个指针j从j=i+1逐一指向i后面的所有字符.就实现了原串的所有子串的遍历(子串为指针i到j中间的部分);最后判断得到的

  • wxPython实现分隔窗口

    本文实例为大家分享了wxPython分隔窗口的具体代码,供大家参考,具体内容如下 1.分割窗口 分隔窗口(wx.SplitterWindow)就是将窗口分成两部分,即左右或上下两部分,如下图所示窗口,整体上分为左右两个窗口,右窗口又分为上下两窗口,两个窗口之间的分隔线是可以拖动的,称为"窗框"(sash). wx.SplitterWindow中一个常用的方法有: SplitVertically(window1, window2, sashPosition=0).设置左右布局的分隔窗口,

  • 利用C语言来求最大连续子序列乘积的方法

    题目描述:给一个浮点数序列,取最大乘积连续子串的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积连续子串为3,0.5,8.也就是说,上述数组中,3 0.5 8这3个数的乘积3*0.5*8=12是最大的,而且是连续的. 提醒:此最大乘积连续子串与最大乘积子序列不同,请勿混淆,前者子串要求连续,后者子序列不要求连续.也就是说:最长公共子串(Longest CommonSubstring)和最长公共子序列(LongestCommon Subsequence,LCS)的区别: 子串(S

  • Python深度学习pytorch神经网络多输入多输出通道

    目录 多输入通道 多输出通道 1 × 1 1\times1 1×1卷积层 虽然每个图像具有多个通道和多层卷积层.例如彩色图像具有标准的RGB通道来指示红.绿和蓝.但是到目前为止,我们仅展示了单个输入和单个输出通道的简化例子.这使得我们可以将输入.卷积核和输出看作二维张量. 当我们添加通道时,我们的输入和隐藏的表示都变成了三维张量.例如,每个RGB输入图像具有 3 × h × w 3\times{h}\times{w} 3×h×w的形状.我们将这个大小为3的轴称为通道(channel)维度.在本节

  • 一文详解typeScript的extends关键字

    目录 前言 extends 的几个语义 extends 与 类型组合/类继承 extends 与类型约束 extends 与条件类型 extends 与 {} extends 与 any extends 与 never extends 与 联合类型 extends 判断类型严格相等 extends 与类型推导 总结 前言 声明: 以下文章所包含的结论都是基于 typeScript@4.9.4 版本所取得的. extends 是 typeScript 中的关键字.在 typeScript 的类型编

  • C++实现leetcode(3.最长无重复字符的子串)

    [LeetCode] 3. Longest Substring Without Repeating Characters 最长无重复字符的子串 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", wit

  • 关于在MFC中将窗口最小化到托盘实现原理及操作步骤

    步骤/方法 (一) 原理 1.最小化的原理:首先要将窗口隐藏,然后在右下角绘制图标. 2.恢复的原理:将窗口显示,再将托盘中的图片删除. (二)程序实现 1.自定义消息WM_SHOWTASK: #define WM_SHOWTASK (WM_USER +1) 2.在MFC的 ::OnSysCommand(UINT nID, LPARAM lParam) 函数体中增加一个命令响应 if(nID==SC_MINIMIZE) ToTray(); //最小化到托盘的函数 3.在消息映射中添加 ON_ME

随机推荐