Minimum Window Substring
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Minimum Window Substring,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2653字,纯文字阅读大概需要4分钟。
内容图文
![Minimum Window Substring](/upload/InfoBanner/zyjiaocheng/1072/aea0898db6614bc088f422614a658dde.jpg)
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>(); 2int count = 0; 3for (int i = 0; i < T.length(); i++) { 4if (!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 } 11int min = Integer.MAX_VALUE; 12int pos = 0; 13int start = -1; 14int end = 0; 15// find first16 Map<Character, Integer> m = new HashMap<Character, Integer>(); 17for(Character c:map.keySet()){ 18 m.put(c, 0); 19 } 20for (; count > 0 && start < S.length() && end < S.length(); ++end) { 21if (m.containsKey(S.charAt(end))) { 22if (start == -1) { 23 start = end; 24 } 25if (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//////////////////////////////////////////////////// 32if (count > 0) { 33return ""; 34 } 35 min = end - start; 36 pos = start; 37 end--; 38for (; start < S.length() && end < S.length();) { 39for(;start<S.length();start++){ 40if(m.containsKey(S.charAt(start))){ 41break; 42 } 43 } 44if(start==S.length()){ 45continue; 46 } 47char temp = S.charAt(start); 48for(++start;start<S.length();start++){ 49if(m.containsKey(S.charAt(start))){ 50break; 51 } 52 } 53if(start==S.length()){ 54continue; 55 } 56if(m.get(temp)>map.get(temp)){ 57if(end-start+1<min){ 58 min = end-start+1; 59 pos=start; 60 } 61 m.put(temp, m.get(temp)-1); 62continue; 63 } 64for(++end;end<S.length();end++){ 65if(S.charAt(end)==temp){ 66break; 67 } 68if(m.containsKey(S.charAt(end))){ 69 m.put(S.charAt(end), m.get(S.charAt(end))+1); 70 } 71 } 72if(end==S.length()){ 73continue; 74 } 75if(end-start+1<min){ 76 min = end-start+1; 77 pos=start; 78 } 79 } 80return S.substring(pos, pos + min);
原文:http://www.cnblogs.com/apoptoxin/p/3747511.html
内容总结
以上是互联网集市为您收集整理的Minimum Window Substring全部内容,希望文章能够帮你解决Minimum Window Substring所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。