leetcode_minimum_window_substring

发表于

难度：Meidum

先讲目标字符串映射到一个目标hash表中，key为字符串，value为字符串出现的次数。
维护一个命中的次数。遍历源字符串，将每一个字符串映射到另一张源hash表中，如果此前该字符串出现的次数小于目标hash表的次数，则命中次数＋1；如果大于等于目标hash表的次数，则命中次数不变化。直到命中次数等于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
39
40
41
42
43
44
45
46
47
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> to_find;
        for(int i = 0; i < t.size(); i++)
            to_find[t[i]]++;
        unordered_map<char,int> found;
        int low = 0;
        int high = 0;
        int min_length = INT_MAX;
        string min_string;
        int count;
        for(int i = 0; i < s.size(); i++)
        {
            if(to_find[s[i]] > 0)
            {
                if(count == 0)
                    low=i;
                if(found[s[i]] < to_find[s[i]])
                    count++;
                found[s[i]]++;
                if(count == t.size())
                {
                    high = i;
                    int j = low;
                    for(; j < high; j++)
                    {
                        if(found[s[j]] > 0)
                        {
                            if(to_find[s[j]] < found[s[j]])
                                found[s[j]]--;
                            else
                                break;
                        }
                    }
                    low = j;
                    if(high-low+1 < min_length)
                    {
                        min_length = high-low+1;
                        min_string = s.substr(low,high-low+1);
                    }
                }
            }
        }
        return min_string;
    }
};