Joyce' Blog
0%

minimum-window-substring

发表于 更新于

题目描述

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。

说明：

  • 如果 S 中不存这样的子串，则返回空字符串 ""。
  • 如果 S 中存在这样的子串，我们保证它是唯一的答案。

题解

滑动窗口、unordered_map

比较棘手的问题：如何判断 window 即子串 s[left…right] 是否符合要求，是否包含 t 的所有字符呢？

参考：https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-tong-yong-si-xiang-by-/

可以用两个哈希表当作计数器解决。用一个哈希表 needs 记录字符串 t 中包含的字符及出现次数，用另一个哈希表 window 记录当前「窗口」中包含的字符及出现的次数，如果 window 包含所有 needs 中的键，且这些键对应的值都大于等于 needs 中的值，那么就可以知道当前「窗口」符合要求了，可以开始移动 left 指针了。

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
#include<unordered_map>
string minWindow(string s, string t) {
	int start = 0, len = s.length()+1;//截取的开始位置与长度
	int left = 0, right = 0;
	unordered_map<char, int> window;//由s获得的字符及次数
	unordered_map<char, int> needs;//由t获得的字符及次数
	for (char c : t)needs[c]++;
	int match = 0;
	while (right < s.length())
	{
		char c = s[right];
		if (needs.count(c))
		{//命中
			window[c]++;
			if (window[c] == needs[c])
				match++;
		}
		right++;
		while (match == needs.size())
		{//更新截取结果，当始终包含t的字符时，left右移
			if ((right - left) < len)
			{
				start = left;
				len = right - left;
			}
			char k = s[left];
			if (needs.count(k))
			{//可能left移到了非关键字母上
				window[k]--;
				if(window[k] < needs[k])//可能有重复积累的
					match--;
			}
			left++;
		}
	}
	if (len > s.length())return "";
	else
		return s.substr(start, len);
}
1
size_type count ( const key_type& key ) const

count函数用以统计key值在unordered_map中出现的次数。c++ unordered_map不允许有重复的key。因此，如果key存在，则count返回1，如果不存在，则count返回0.

Tomorrow：

PA1报告、项目总结书、心理学视频。