3.4 Hot100刷题记录

76. 最小覆盖子串

最后一题
滑动窗口，要不还是把我杀了吧

class Solution {
public:
    bool isCover(int s[], int t[]) {
        for(int i = 0; i < 64; i++) {
            if(s[i] < t[i]) return false;
        }
        return true;
    }

    string minWindow(string s, string t) {
        if(s.size() < t.size()) return "";

        int left = 0;
        int right = -1;
        int edge[2] = { -1, int(s.size()) + 1 }; 
       

        int s_freq[64] = {0};
        int t_freq[64] = {0};

        for(int i = 0; i < t.size(); i++) {
            t_freq[t[i] - 'A']++;
        }

        while(left <= (s.size() - t.size())) {
            if((right - left + 1) < t.size()) {
                if(right + 1 < s.size()) {
                    s_freq[s[++right] - 'A']++;
                    continue;
                }else break;
            }
            if(!isCover(s_freq, t_freq)) {
                if(right + 1 < s.size()) {
                    s_freq[s[++right] - 'A']++;
                }else {
                    s_freq[s[left++] - 'A']--;
                }
            }else {
                if(right - left + 1 == t.size()) return s.substr(left, t.size());
                else {
                    if(right - left < edge[1] - edge[0]) {
                        edge[0] = left;
                        edge[1] = right;
                    }
                    s_freq[s[left++] - 'A']--;
                }
            }

        }

        return edge[0] == -1 ? "" : s.substr(edge[0], edge[1] - edge[0] + 1);

    }
};
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54