leetcode76 Minimum Window Substring

给定两个字符串s和t， 找到s的一个子串，使得t的每个字符都出现在子串中，求最短的子串

由于要每个字符出现，所以顺序其实没有关系
因此我们可以定义一个map，统计t中字符出现次数
然后在s中慢慢挪动滑动窗口，如果符合要求就缩短滑动窗口，直到不符合，然后继续移动

class Solution {
public:
    string minWindow(string s, string t) {
        int ans = -1, ans_len = -1, n = s.size(), m = t.size();
        if(n < m)return "";
        unordered_map<char, int> mp;
        for(char& c:t)++mp[c];
        int cnt = mp.size(), pre = 0;
        for(int i = 0; i < n; ++i){
            auto it = mp.find(s[i]);
            if(it == mp.end())continue;
            --it->second;
            if(it->second == 0){
                --cnt;
                if(cnt == 0){
                    if(m == 1)return t;
                    if(ans_len == -1 || i - pre + 1 < ans_len){
                        ans_len = i - pre + 1;
                        ans = pre;
                    }
                    while(pre < i){
                        auto it2 = mp.find(s[pre]);
                        ++pre;
                        if(it2 == mp.end()){
                            if(i - pre + 1 < ans_len){
                                ans_len = i - pre + 1;
                                ans = pre;
                            }
                            continue;
                        }
                        ++it2->second;
                        if(it2->second == 1){
                            ++cnt;
                            break;
                        }
                        else{
                            if(i - pre + 1 < ans_len){
                                ans_len = i - pre + 1;
                                ans = pre;
                            }
                        }
                    }
                    
                    while(pre < i){
                        auto it2 = mp.find(s[pre]);
                        if(it2 == mp.end()){
                            ++pre;
                            continue;
                        }
                        else{
                            break;
                        }
                    }
                }
            }
        }
        
        if(ans == -1)return "";
        return s.substr(ans, ans_len);
    }
};
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
55
56
57
58
59
60
61