首页 > 代码库 > Minimum Window Substring
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).
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.
直接说思路吧,就是先统计T串中有多少个字符,分别出现了多少次,保存在Map map中,然后在S中找到第一个包含T中全部字符的串,设起始位置为start,结束位置为end。并记录下这个子串中T中每个字符出现的次数,保存在Map m中。
然后从start+1开始向后找到第一个在T中出现的字符,用char temp记录该字符,然后start向后找到第一个在T中出现的字符,若temp在m中出现次数大于在map中出现的次数,则比较end-start+1与min的大小并更新,否则end向后找到第一个等于temp的字符,然后更新min。
因为start和end都是从0到S.length遍历一次并且没有回溯,因此复杂度为O(n)。代码如下:
1 Map<Character, Integer> map = new HashMap<Character, Integer>(); 2 int count = 0; 3 for (int i = 0; i < T.length(); i++) { 4 if (!map.containsKey(T.charAt(i))) { 5 map.put(T.charAt(i), 1); 6 }else{ 7 map.put(T.charAt(i), map.get(T.charAt(i))+1); 8 } 9 count++; 10 } 11 int min = Integer.MAX_VALUE; 12 int pos = 0; 13 int start = -1; 14 int end = 0; 15 // find first 16 Map<Character, Integer> m = new HashMap<Character, Integer>(); 17 for(Character c:map.keySet()){ 18 m.put(c, 0); 19 } 20 for (; count > 0 && start < S.length() && end < S.length(); ++end) { 21 if (m.containsKey(S.charAt(end))) { 22 if (start == -1) { 23 start = end; 24 } 25 if (m.get(S.charAt(end)) < map.get(S.charAt(end))) { 26 count--; 27 } 28 m.put(S.charAt(end), m.get(S.charAt(end)) + 1); 29 } 30 } 31 //////////////////////////////////////////////////// 32 if (count > 0) { 33 return ""; 34 } 35 min = end - start; 36 pos = start; 37 end--; 38 for (; start < S.length() && end < S.length();) { 39 for(;start<S.length();start++){ 40 if(m.containsKey(S.charAt(start))){ 41 break; 42 } 43 } 44 if(start==S.length()){ 45 continue; 46 } 47 char temp = S.charAt(start); 48 for(++start;start<S.length();start++){ 49 if(m.containsKey(S.charAt(start))){ 50 break; 51 } 52 } 53 if(start==S.length()){ 54 continue; 55 } 56 if(m.get(temp)>map.get(temp)){ 57 if(end-start+1<min){ 58 min = end-start+1; 59 pos=start; 60 } 61 m.put(temp, m.get(temp)-1); 62 continue; 63 } 64 for(++end;end<S.length();end++){ 65 if(S.charAt(end)==temp){ 66 break; 67 } 68 if(m.containsKey(S.charAt(end))){ 69 m.put(S.charAt(end), m.get(S.charAt(end))+1); 70 } 71 } 72 if(end==S.length()){ 73 continue; 74 } 75 if(end-start+1<min){ 76 min = end-start+1; 77 pos=start; 78 } 79 } 80 return S.substring(pos, pos + min);