【剑指offer专项】17. 含有所有字符的最短字符串

思路：

对应的代码和注释

​

class Solution {
public:
	string minWindow(string s, string t) {
		vector<int>cnt(58);//A-z字母表
		string res;
		//用字母表记录基串的字母数
		for (int i = 0; i < t.length(); i++)
		{
			--cnt[t[i] - 'A'];
		}

		int diff = 0;//用diff记录子串中相对基串不够的字母数
		for (int i = 0; i < 58; i++)
		{
			if (cnt[i] < 0)diff += 1;
		}
	
		int  high = 0,len=INT_MAX;
		//滑动窗口
		for (int low = 0; low < s.length(); low++)
		{
			if (diff == 0) {//移动low指针，需验证更新最短子串
				if ((high - low) < len ? 1 : 0)
				{
					res = s.substr(low, high - low);
					len = high - low;
				}
			}
			while (high< s.length()&& diff!=0)
			{
				//移动high指针 子串进元素
				//进元素后,导致子串不足字母少1，diff-1,
				++cnt[s[high] - 'A'];
				if (cnt[s[high] - 'A'] == 0)
				{
					diff -= 1;
				}
				high++;

				if (diff == 0) {//找到满足要求的子串，更新最短子串
					if ((high-low)<len?1:0)
					{
						res=s.substr(low,high-low);
						len = high - low;
					}
					break;
				}
			}
			//子串出元素
			--cnt[s[low] - 'A'];
			//若出元素后，导致子串不足字母多1，diff+1
			if (cnt[s[low] - 'A'] == -1)
			{
				diff += 1;
			}
		}
		return res;
	}
};

​