Minimum Window Substring
public class Solution { public String minWindow(String s, String t) { int[] needtofind = new int[256]; int[] hasfound = new int[256]; for(int i = 0 ; i < t.length(); i++) { needtofind[t.charAt(i)]++; } int start = 0; int count = 0; int min = Integer.MAX_VALUE; String window = ""; for(int end = 0; end < s.length(); end++) { if(needtofind[s.charAt(end)] == 0)//如果不需要 continue; char e = s.charAt(end); hasfound[e]++; // 找到一个需要的 if(hasfound[e] <= needtofind[e]) count++; if(count == t.length()){//如果找到全部的 char st = s.charAt(start); while(needtofind[st] == 0 || hasfound[st] > needtofind[st]){ if(hasfound[st] > needtofind[st]) hasfound[st] --; st = s.charAt(++start); } if(end - start + 1 < min){ min = end - start + 1; window = s.substring(start, end+1); } } } return window; } }
Leave A Comment