Minimum Window Substring 最小窗口子串问题
发布时间:2020-12-14 02:33:28 所属栏目:Windows 来源:网络整理
导读: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 c
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:
? 思路:使用到了滑动窗口,再使用Map保存目前已经匹配的目标字符串t中的元素个数。使用一个窗口(left,right)依次向右遍历。先是窗口一直向右扩张,直到(left,right)中包含目标字符串t中的所以元素的时候。 Left再向右缩,来得到最小窗口。 ? 1 public class Minimum_Window_Substring { 2 public static String minWindow(String s,String t) { 3 if(null==s||s.length()<t.length()||s.length()==0){ 4 return ""; 5 } 6 7 Map<Character,Integer> map = new HashMap<>(); 8 int Left = 0; 9 int minLeft = 0; 10 int count = 0; 11 int minLen = s.length()+1; 12 13 for(char c:t.toCharArray()){ 14 if(map.containsKey(c)){ 15 map.put(c,map.get(c)+1); 16 }else{ 17 map.put(c,1); 18 } 19 } 20 21 for(int right = 0;right<s.length();right++){ 22 if(map.containsKey(s.charAt(right))){ 23 map.put(s.charAt(right),map.get(s.charAt(right))-1); 24 //统计当前包含在t中的字母,如果s.charAt(right)在t中,则count++ 25 if(map.get(s.charAt(right))>=0){ 26 count++; 27 } 28 29 //当t中的元素都包含的时候 30 while(count==t.length()){ 31 //查看当前的(Left,right)长度是否更小 32 if(right - Left +1<minLen){ 33 minLeft = Left; 34 minLen = right - Left +1; 35 } 36 37 //如果当前左边界包含在目标字符串t中的元素,那么则将其释放,向后遍历看是否还能匹配到更短串 38 if(map.containsKey(s.charAt(Left))){ 39 map.put(s.charAt(Left),map.get(s.charAt(Left))+1); 40 if(map.get(s.charAt(Left))>0){ 41 count--; 42 } 43 } 44 //缩小窗口左边界 45 Left++; 46 } 47 48 } 49 } 50 51 if(s.length()<minLen){ 52 return ""; 53 } 54 55 return s.substring(minLeft,minLeft+minLen); 56 } 57 58 public static void main(String[] args) { 59 System.out.println(minWindow("ADOBECODEBANC","ABC")); 60 } 61 } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- 验证 – Windows DLL是否由Microsoft签名?我能否发现他们是
- 是否可以重命名Windows Azure的托管服务
- 如何阻止Mingw(g)在Windows中打开控制台窗口
- 将Uint8Array转换为node.js中的十六进制字符串等效项
- Windows 10 iSCSI Boot
- windows-update – 如何在我的网络上完全阻止Windows Updat
- 如何在Windows上获取磁盘标识符?
- tfs – 我们如何在MSBuild创建的msdeploy包中包含ajaxmin创
- windows – 关闭前向所有用户发送消息
- 如何使用wamp在windows上烘焙cakephp 2.0应用程序