【leetcode】76 Minimum Window Substring

描述

给定一个字符串S和一个字符串T，找到S中的最子字符串，它将包含复杂度为T的所有字符

样例

样例1

输入: S = "KKADOBECODEBANC", T = "ABC"
输出: "BANC"

思路

双指针，这个代码是讨论区复制过来的，感觉好巧妙，两个调整 count 的地方很巧妙，一来一去最后将会等于原来 map 中的值。

代码

class Solution {
public:
    string minWindow(string s, string t) {
        int start = 0,end = 0,head = 0; // head tail, Two pointer
        int count = t.size();// make sure the substring is valid
        int maxLen = INT_MAX;
        vector<int> maps (128,0);
        for(auto c:t) maps[c]++;
        while(end<s.size()){
            if(maps[s[end++]]-- >0){count--;}  // s[i] is in t
            while(count==0){ //the substring is valid now
                if(end-start < maxLen) maxLen = end - (head=start) ;
                if(maps[s[start++]]++ ==0) count++; //make it invalid
            }
        }
        return maxLen == INT_MAX?"":s.substr(head,maxLen);
    }
};

参考

原题链接

---