友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
76. Minimum Window Substring
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example:
Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"
Note:
-
If there is no such window in S that covers all characters in T, return the empty string "".
-
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
思路分析
滑动窗口
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
* Runtime: 489 ms, faster than 5.03% of Java online submissions for Minimum Window Substring.
* Memory Usage: 322.8 MB, less than 5.32% of Java online submissions for Minimum Window Substring.
*
* ↓ 优化：在最后输出时，才截取字符串。
*
* Runtime: 33 ms, faster than 16.02% of Java online submissions for Minimum Window Substring.
* Memory Usage: 44.4 MB, less than 5.32% of Java online submissions for Minimum Window Substring.
*/
public String minWindow(String s, String t) {
if (Objects.isNull(s) || s.length() == 0
|| Objects.isNull(t) || t.length() == 0
|| s.length() < t.length()) {
return "";
}
Map<Character, Integer> needs = new HashMap<>(t.length());
for (char c : t.toCharArray()) {
needs.put(c, needs.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int minLength = Integer.MAX_VALUE;
int start = 0;
int match = 0;
Map<Character, Integer> windows = new HashMap<>(t.length());
while (right < s.length()) {
char rChar = s.charAt(right);
if (needs.containsKey(rChar)) {
int rCount = windows.getOrDefault(rChar, 0) + 1;
windows.put(rChar, rCount);
if (rCount == needs.get(rChar)) {
match++;
}
}
right++;
while (match == needs.size()) {
if (right - left < minLength) {
minLength = right - left;
start = left;
}
char lChar = s.charAt(left);
if (needs.containsKey(lChar)) {
int lCount = windows.get(lChar) - 1;
windows.put(lChar, lCount);
if (lCount < needs.get(lChar)) {
match--;
}
}
left++;
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(start, start + minLength);
}
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* 自己实现失败后，参考社区答案修改的
*/
public String minWindow(String s, String t) {
if (s == null || s.isEmpty() || t == null || t.isEmpty() || s.length() < t.length()) {
return "";
}
// 初始化 need，记录 t 中每个字符的出现次数
char[] chars = s.toCharArray();
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0; // 窗口的左右边界
int valid = 0; // 已经匹配上的字符数量
int start = 0, minLen = Integer.MAX_VALUE; // 最小窗口的起始位置和长度
while (right < s.length()) {
// 扩大窗口
char rc = chars[right];
right++;
// 更新窗口内字符的计数
if (need.containsKey(rc)) {
window.put(rc, window.getOrDefault(rc, 0) + 1);
if (window.get(rc).equals(need.get(rc))) {
valid++;
}
}
// 收缩窗口
while (need.size() == valid) {
// 更新最小窗口的起始位置和长度
if (right - left < minLen) {
start = left;
minLen = right - left;
}
char lc = chars[left];
// 缩小窗口，移动左边界
if (need.containsKey(lc)) {
window.put(lc, window.get(lc) - 1);
if (window.get(lc) < need.get(lc)) {
valid--;
}
}
left++;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}