首页 > 代码库 > [Leetcode] Minimum Window Substring
[Leetcode] Minimum Window Substring
算法思想: http://www.cnblogs.com/lichen782/p/leetcode_minimum_window_substring_3.html
1 public class Solution { 2 public String minWindow(String S, String T) { 3 int N = S.length(); 4 int M = T.length(); 5 if(N < M) 6 return ""; 7 int[] need=new int[256]; 8 int[] find=new int[256]; 9 for(int i=0;i<M;++i)10 need[T.charAt(i)]++;11 12 int count=0;13 int resStart=-1;14 int resEnd=N;15 16 for(int start=0,end=0;end<N;++end){17 if(need[S.charAt(end)]==0)18 continue;19 if(find[S.charAt(end)]<need[S.charAt(end)])20 count++;21 find[S.charAt(end)]++;22 if(count!=M)23 continue;24 25 for(;start<end;++start){26 if(need[S.charAt(start)]==0)27 continue;28 if(find[S.charAt(start)]<=need[S.charAt(start)])29 break;30 find[S.charAt(start)]--;31 }32 if(end-start<resEnd-resStart){33 resStart=start;34 resEnd=end;35 }36 }37 return (resStart==-1)?"":S.substring(resStart, resEnd+1);38 }39 }
[Leetcode] Minimum Window Substring
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。