05 August 2008
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:
1
2
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"
Note:
1
""
要求在字符串s中找到最小的子字符串w（window），其中包含T中所有的字符，如果没有就返回空字符串，如果有，最小的字符串只有唯一的一个。
Labuladuodong的双指针模板，用两个HashMap，比较好理解的做法
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
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> needs = new HashMap<>(); // target - t中字符的出现次数
HashMap<Character, Integer> window = new HashMap<>(); // 窗口中相应“有效”字符的出现次数
for (char ch : t.toCharArray()) {
needs.put(ch, needs.getOrDefault(ch, 0) + 1);
}
int left = 0, right = 0; // 窗口的左右边界初始为零[left, right)
int valid = 0; // 窗口中满足在needs的字符个数
// 记录最小覆盖字串的起始索引及长度
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
// ch是准备进入窗口的字符
char ch = s.charAt(right);
// 得到ch后右移窗口，相当于寻找一个【可行解】
right++;
// 更新窗口内的一系列数据
if (needs.containsKey(ch)) {//target-t中需要该字符
window.put(ch, window.getOrDefault(ch, 0) + 1);
// 该字符在window中的数量已经等于（满足）了target-t中该字符
if (window.get(ch).equals(needs.get(ch))) {
valid++;
}
}
// 判断窗口左侧是否需要收紧，以此来优化【可行解】，得到最优解
// valid已经达到target中所有字符的数量，表示找到一个s中的子字符串包含全部t中字符
// 注意这里是hashmap的size而不是t的leng，因为可能有重复元素
while(valid == needs.size()) {
//更新最小覆盖字串
if (right - left < len) { //遇到更小的字串
start = left;
len = right - left;
}
// 准备移除窗口的字符
char de = s.charAt(left);
// 移动窗口左侧缩小窗口
left++;
// 更新窗口内的一系列数据，窗口左边遇到一个“有效”字符
if (needs.containsKey(de)) {
if (window.get(de).equals(needs.get(de))) {
valid--;
}
window.put(de, window.get(de) - 1); // 该有效字符减少一次
}
}
}
// 返回最小覆盖字串
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}
使用HashMap和Deque
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) {
// By default the window is the entire string...
int bestMin = 0;
int bestMax = s.length() -1;
// This holds the amount of each character we need to see
Map<Character, Integer> charCount = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
Integer count = charCount.getOrDefault(c, 0);
charCount.put(c, count+1);
}
// This holds characters and their last seen indexes in the string
Map<Character, Deque<Integer>> lastSeen = new HashMap<>();
// This holds characters that we have seen the minimum amount of
Set<Character> seenMin = new HashSet<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// check if this is a character we are looking for
if (charCount.containsKey(c)) {
Deque<Integer> positions = lastSeen.getOrDefault(c, new LinkedList<>());
// If we have stored the maximum positions, remove the earliest and add the newest to the end
if (positions.size() == charCount.get(c)) {
positions.removeFirst();
}
positions.addLast(i);
if (positions.size() == charCount.get(c)) {
seenMin.add(c);
}
lastSeen.put(c, positions);
// If we have seen all our characters the minimum amount of times
// we can try and calculate the minimum total length that holds all those characters
if (seenMin.size() == charCount.size()) {
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// Iterate over the positions for each character and grab their min/max positions
for (Deque<Integer> values : lastSeen.values()) {
min = Math.min(min, values.getFirst());
max = Math.max(max, values.getLast());
}
// If we have a smaller length than our current best length, save it.
if (max - min < bestMax - bestMin) {
bestMax = max;
bestMin = min;
}
}
}
}
// If we have seen all of our characters the minimum amount of times we know we will have a valid solution
if (seenMin.size() == charCount.size()) {
return s.substring(bestMin, bestMax+1);
} else {
return "";
}
}
}