[LeetCode]Minimum Window Substring

和之前各种sliding window的题都是类似的，区别就是这一题策略稍微不同，要求最短的，所以我们每次就得尽量将左边界右移，具体策略如下：

• 如果当前s的substring没有包含t的所有字符，右移右边界
• 如果包含了t的所有字符，假设左边界对应的字符为left
• 如果substring中left的数量大于t中的数量，右移左边界
• 如果left不为t中的字符，右移左边界

这样可以保证我们每次找到满足条件最短的，时间复杂度O(n)，空间复杂度O)(n)，代码如下：

	class Solution {
	public:
	string minWindow(string s, string t) {
	int lenS = s.size(), lenT = t.size(), left = 0, count = 0;
	string res = "";
	unordered_map<char, int> map, curr;
	for(auto c : t)++map[c];
	for(int i = 0; i < lenS; ++i)
	{
	if(map.find(s[i]) != map.end())
	{
	++curr[s[i]];
	if(curr[s[i]] <= map[s[i]])++count;
	while(count == t.size() && (map.find(s[left]) == map.end() || curr[s[left]] > map[s[left]]))
	{
	char c = s[left++];
	if(map.find(c) != map.end())--curr[c];
	}
	}
	if(count == t.size())
	res = res.empty()? s.substr(left, i - left + 1): (res.size() > i - left + 1? s.substr(left, i - left + 1): res);
	}
	return res;
	}
	};

view raw Minimum Window Substring.cpp hosted with ❤ by GitHub