题

Minimum Window Substring

题解

看完Minimum Window Substring【FLAG高频精选面试题讲解】中小姐姐讲的例子，就可以明白此题的思路。

本题为滑动窗口问题，通过hashmap+快慢指针来解决。

针对本题，slow和fast为快慢指针，match_count代表字符串T在字符串S中匹配字符的数目，min_len代表the size of the minimum window in S which will contain all the characters in T，index代表最小滑动窗口的开始地址。

代码是按照Minimum Window Substring【FLAG高频精选面试题讲解】来写的。

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
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hashmap;
        for(int i = 0; i < t.size(); ++i){
            if(!hashmap.count(t[i]))
                hashmap[t[i]] = 1;
            else
                hashmap[t[i]]++;
        }
        int slow = 0, fast = 0, match_count = 0, min_len= INT_MAX, index;
        for(fast = 0; fast < s.size(); ++fast){
            char ch = s[fast];
            if(!hashmap.count(ch))
                continue;
            int count  = hashmap[ch];
            hashmap[ch]--;
            // match another character
            if(count == 1) //1->0
                match_count++;
            while(match_count == hashmap.size()){
                // find a valid substring
                if(fast - slow + 1 < min_len){
                    min_len = fast - slow + 1;
                    index = slow;
                }
                char leftmost = s[slow];
                slow++;
                if(!hashmap.count(leftmost))
                    continue;
                int leftmostCount = hashmap[leftmost];
                hashmap[leftmost]++;
                if(leftmostCount == 0) // 0->1
                    match_count--;
            }
        }   
        
        return min_len == INT_MAX ? "" : s.substr(index, min_len);
        
    }
};

参考资料:

  1. Minimum Window Substring【FLAG高频精选面试题讲解】
  2. Here is a 10-line template that can solve most ‘substring’ problems