-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMinimumWindowSubstring.java
More file actions
70 lines (68 loc) · 2.49 KB
/
MinimumWindowSubstring.java
File metadata and controls
70 lines (68 loc) · 2.49 KB
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
package com.yangchd.leetcode.hard;
import java.util.HashMap;
/**
* @author yangchd 2018/11/5.
*
* 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.
*
*/
public class MinimumWindowSubstring {
/**
* 处理这种问题，把目标字符串放入map中，并计数
* 当所有的数量均为0时，判断长度。
* 完成一次查找以后，将最前面的数去掉，然后往后继续找，最终得到最短的
*/
class Solution {
public String minWindow(String s, String t) {
if (s == null || s.length() < t.length() || s.length() == 0) {
return "";
}
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (char c : t.toCharArray()) {
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
} else {
map.put(c, 1);
}
}
int left = 0;
int minLeft = 0;
int minLen = s.length() + 1;
int count = 0;
for (int right = 0; right < s.length(); right++) {
if (map.containsKey(s.charAt(right))) {
map.put(s.charAt(right), map.get(s.charAt(right)) - 1);
if (map.get(s.charAt(right)) >= 0) {
count++;
}
while (count == t.length()) {
if (right - left + 1 < minLen) {
minLeft = left;
minLen = right - left + 1;
}
if (map.containsKey(s.charAt(left))) {
map.put(s.charAt(left), map.get(s.charAt(left)) + 1);
if (map.get(s.charAt(left)) > 0) {
count--;
}
}
left++;
}
}
}
if (minLen > s.length()) {
return "";
}
return s.substring(minLeft, minLeft + minLen);
}
}
}