Minimum Window Substring（C++最小覆盖子串）

左手的ㄟ右手 2022-10-11 13:42 168阅读 0赞

（1）map+双指针

class Solution {
    public:
        string minWindow(string s, string t) {
            unordered_map<char,int> mp,mp1;
            for(int i=0;i<t.length();i++) {
                mp[t[i]]++;
                mp1[t[i]]++;
            }
    
            int count=0,minlen=INT_MAX,start=0;
            int index=0;
            for(int i=0;i<s.length();i++) {
                if(mp.find(s[i])!=mp.end()) {
                    if(mp[s[i]]<2*mp1[s[i]]) {
                        count++;
                        mp[s[i]]++;
    
                        if(count==t.length()) {
                            while(start<=i) {
                                if(mp.find(s[start])==mp.end()) start++;
                                else if(mp[s[start]]>2*mp1[s[start]]) {
                                    mp[s[start]]--;
                                    start++;
                                } else if(i-start+1<minlen) {
                                    minlen=i-start+1;
                                    index=start;
                                    mp[s[start]]--;
                                    start++;
                                    break;
                                } else {
                                    mp[s[start]]--;
                                    start++;
                                    break;
                                }
                            }
                            count--;
                        }
                    } else mp[s[i]]++;
                }
            }
    
            if(minlen!=INT_MAX) return s.substr(index,minlen);
            else return "";
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

相关 76. 最小覆盖子串

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

深藏阁楼爱情的钟/ 2023年10月04日 10:26/ 0 赞/ 47 阅读

相关 76最小覆盖子串

一、前言标签：字符串滑动窗口。问题来源LeetCode 76 难度：困难。问题链接：[https://leetcode-cn.com/problems/mini

系统管理员/ 2023年03月01日 11:54/ 0 赞/ 26 阅读

相关最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。示例：输入: S = "ADOBECODEBANC", T = "ABC"

矫情吗；*/ 2023年02月11日 13:29/ 0 赞/ 20 阅读

相关 299-最小覆盖子串

题目如下：给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。示例：

Dear 丶/ 2023年01月17日 03:21/ 0 赞/ 205 阅读

相关（Java）leetcode-76 Minimum Window Substring（最小覆盖子串）

题目描述给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。注意：

你的名字/ 2022年12月21日 04:43/ 0 赞/ 212 阅读

相关 LeetCode 76. 最小覆盖子串

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

系统管理员/ 2022年11月07日 05:55/ 0 赞/ 239 阅读

相关 76. 最小覆盖子串

链接：[https://leetcode-cn.com/problems/minimum-window-substring/][https_leetcode-cn.com_pr

电玩女神/ 2022年10月13日 01:55/ 0 赞/ 226 阅读

相关 Minimum Window Substring（C++最小覆盖子串）

（1）map+双指针 class Solution { public: string minWindow(string s, string t

左手的ㄟ右手/ 2022年10月11日 13:42/ 0 赞/ 169 阅读

相关 76. 最小覆盖子串

先上滑动窗口模板 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubm

﹏ヽ暗。殇╰゛Y/ 2022年10月09日 12:10/ 0 赞/ 224 阅读

相关 LeetCode : 76. Minimum Window Substring 最小窗口子串

试题 Given a string S and a string T, find the minimum window in S which will contain al

约定不等于承诺〃/ 2021年06月24日 16:11/ 0 赞/ 403 阅读