-
Notifications
You must be signed in to change notification settings - Fork 0
/
76. 最小覆盖子串.java
71 lines (70 loc) · 2.31 KB
/
76. 最小覆盖子串.java
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
int[] count = new int[128];
for (char c : t.toCharArray()) {
count[c]++;
}
int start = 0, len = Integer.MAX_VALUE;
int total = 0;
for (int l = 0, r = 0; r < s.length(); r++) {
if (count[s.charAt(r)]-- > 0) {
total++;
}
while (total == t.length()) {
if (r - l + 1 < len) {
len = r - l + 1;
start = l;
}
count[s.charAt(l)]++;
if (count[s.charAt(l)] > 0) {
total--;
}
l++;
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
/*class Solution {
public String minWindow(String s, String t) {
if (s.length() == 0 || t.length() == 0) {
return "";
}
Map<Character, Integer> mapT = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
int count = mapT.getOrDefault(t.charAt(i), 0);
mapT.put(t.charAt(i), count + 1);
}
int size = mapT.size();
int formed = 0;
int l = 0, r = 0;
int[] ans = { -1, 0, 0 };
Map<Character, Integer> windowsCount = new HashMap<>();
while (r < s.length()) {
char c = s.charAt(r);
int count = windowsCount.getOrDefault(c, 0);
windowsCount.put(c, count + 1);
if (mapT.containsKey(c) && mapT.get(c).intValue() == windowsCount.get(c).intValue()) {
formed++;
}
while (l <= r && formed == size) {
if (ans[0] == -1 || r - l + 1 < ans[0]) {
ans[0] = r - l + 1;
ans[1] = l;
ans[2] = r;
}
c = s.charAt(l);
windowsCount.put(c, windowsCount.get(c) - 1);
if (mapT.containsKey(c) && mapT.get(c).intValue() > windowsCount.get(c).intValue()) {
formed--;
}
l++;
}
r++;
}
return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
}
}*/