6/20/2014

138. 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 count = 0;
        int minWindowSize = Integer.MAX_VALUE;
        int start = 0;
        int end = 0;
        String minWindow = "";
       
        for (end=0; end<S.length(); end++) {
            if (needToFind[S.charAt(end)]==0) continue;
           
            char c = S.charAt(end);
            hasFound[c]++;
           
            if (hasFound[c]<=needToFind[c]) count++;
           
            if (count==T.length()) {
                while (needToFind[S.charAt(start)]==0 || hasFound[S.charAt(start)]>needToFind[S.charAt(start)]) {
                    if (hasFound[S.charAt(start)]>needToFind[S.charAt(start)]) hasFound[S.charAt(start)]--;
                    start++;
                }
               
                if (end-start+1<minWindowSize) {
                    minWindowSize = end-start+1;
                    minWindow = S.substring(start, end+1);
                }
            }
        }
       
        return minWindow;
    }
}

没有评论:

发表评论