Minimum Window Substring leetcode java
题目:
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).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC"
.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string ""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
题解:
这道题也是用滑动窗口的思想,思想跟 Substring with Concatenation of All Words是一样的,同样是利用HashMap来存Dict,然后来遍历整个母串。因为这里是要求最短的包含子串的字符串,所以中间是可以允许有非子串字符的,当遇见非子串字符而count又没到子串长度时,可以继续走。
当count达到子串长度,说明之前遍历的这些有符合条件的串,用一个pre指针帮忙找,pre指针帮忙找第一个在HashMap中存过的,并且找到后给计数加1后的总计数是大于0的,判断是否为全局最小长度,如果是,更新返回字符串res,更新最小长度,如果不是,继续找。
这道题的代码也参考了code ganker的。
代码如下:
2 String res = "";
3 if(S == null || T == null || S.length()==0 || T.length()==0)
4 return res;
5
6 HashMap<Character, Integer> dict = new HashMap<Character, Integer>();
7 for(int i =0;i < T.length(); i++){
8 if(!dict.containsKey(T.charAt(i)))
9 dict.put(T.charAt(i), 1);
10 else
11 dict.put(T.charAt(i), dict.get(T.charAt(i))+1);
12 }
13
14 int count = 0;
15 int pre = 0;
16 int minLen = S.length()+1;
17 for(int i=0;i<S.length();i++){
18 if(dict.containsKey(S.charAt(i))){
19 dict.put(S.charAt(i),dict.get(S.charAt(i))-1);
20 if(dict.get(S.charAt(i)) >= 0)
21 count++;
22
23 while(count == T.length()){
24 if(dict.containsKey(S.charAt(pre))){
25 dict.put(S.charAt(pre),dict.get(S.charAt(pre))+1);
26
27 if(dict.get(S.charAt(pre))>0){
28 if(minLen>i-pre+1){
29 res = S.substring(pre,i+1);
30 minLen = i-pre+1;
31 }
32 count--;
33 }
34 }
35 pre++;
36 }
37 }//end for if(dict.containsKey(S.charAt(i)))
38 }
39 return res;
40 }
Reference:
http://blog.csdn.net/linhuanmars/article/details/20343903
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。