Cinte's Leetcode Record
0%

76. Minimum Window Substring

Posted on Edited on In Disqus:
Symbols count in article: 2k Reading time ≈ 2 mins.

76. Minimum Window Substring

使用了之前sliding window的范式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    string minWindow(string s, string t) {
        int begin = 0;
        int end = 0;
        pair<int, int> ret{0, 0};
        int curMax = s.size() + 1;
        unordered_map<char, int> map;
        for(auto& ch : t)
            map[ch] += 1;
        int count = map.size();
        while(end < s.size())
        {
            if(map.find(s[end]) != map.end())
            {
                --map[s[end]];
                if(!map[s[end]])
                    --count; 
            }
            ++end;
            while(!count)
            {
                if(map.find(s[begin]) != map.end())
                {
                    ++map[s[begin]];
                    if(map[s[begin]] > 0)
                        ++count;
                }
                if(end - begin < curMax)
                {
                    curMax = end - begin;
                    ret.first = begin;
                    ret.second = curMax;
                }
                ++begin;
            }
        }
        return s.substr(ret.first, ret.second);
    }
};
filtered

只记录存在于t中的字符的坐标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> map;
        for(auto& ch : t)
            map[ch] += 1;
        
        vector<pair<char, int>> newS;
        for(int i = 0; i < s.size(); ++i)
        {
            if(map.find(s[i]) != map.end())
                newS.push_back(pair<char, int>{s[i], i});
        }
        int begin = 0, end = 0;
        int count = map.size();
        int curWindow = s.size();
        int ansL = 0, ansR = 0;
        while(end < newS.size())
        {
            if(--map[newS[end].first] == 0)
                --count;
            while(!count)
            {
                if(newS[end].second - newS[begin].second < curWindow)
                {
                    ansL = newS[begin].second;
                    ansR = newS[end].second + 1;
                    curWindow = ansR - ansL;
                }
                if(++map[newS[begin].first] > 0)
                    ++count;
                ++begin;
            }
            ++end;
        }
        return s.substr(ansL, ansR - ansL);
    }
};

review 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size();
        unordered_map<char, int> map;
        for(auto ch : t)
            ++map[ch];
        int count = map.size();
        int begin = 0, end = 0;
        int rl = 0;
        int subSize = INT_MAX;
        while(end < n)
        {
            if(--map[s[end]] == 0)
                --count;
            while(count == 0)
            {
                if(end - begin + 1 < subSize)
                {
                    rl = begin;
                    subSize = end - begin + 1;
                }
                if(++map[s[begin]] > 0)
                    ++count;
                ++begin;
            }
            ++end;
        }
        if(subSize == INT_MAX)
            return "";
        return s.substr(rl, subSize);
    }
};