1.题目描述
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).
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
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.
说明：
- 如果 S 中不存这样的子串，则返回空字符串
""。
- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
2.Solutions
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
|
public String (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);
}
|
（完）
近期评论