[Lintcode]Minimum Window Substring，lintcodeminimum

[Lintcode]Minimum Window Substring，lintcodeminimum

Given a string source and a string target, find the minimum window in source which will contain all the characters in target.

Example

For source = "ADOBECODEBANC", target = "ABC", the minimum window is "BANC"

分析：滑动窗口法。右侧向右滑动，知道所有字符都找到。然后左侧向右滑动。知道有字符丢失而无法匹配。然后再次滑动右侧。

算法写的比较复杂。待优化

public class Solution {
    /**
     * @param source: A string
     * @param target: A string
     * @return: A string denote the minimum window
     *          Return "" if there is no such a string
     */
    public String minWindow(String source, String target) {
        HashMap<Character, Integer> res = new HashMap<Character, Integer>();
        int rest = target.length();
        for(int i = 0; i < target.length(); i++) {
            if(!res.containsKey(target.charAt(i))) res.put(target.charAt(i), 1);
            else res.put(target.charAt(i), res.get(target.charAt(i)) + 1);
        }
        int start = 0, curr = 0;
        String str = new String(source);
        boolean found = false;
        while(curr < source.length() && start <= curr) {
            char c = source.charAt(curr);
            if(target.indexOf("" + c) != -1){
                if(res.get(source.charAt(curr)) > 0) rest -= 1;
                res.put(source.charAt(curr), res.get(source.charAt(curr)) - 1);
                
                if(rest == 0) {
                    while(target.indexOf(source.charAt(start)) == -1 || 
                    res.get(source.charAt(start)) < 0) {
                        if(res.get(source.charAt(start)) != null &&
                            res.get(source.charAt(start)) < 0)
                            res.put(source.charAt(start), res.get(source.charAt(start)) + 1);
                        start++;
                    }
                    String tmp = source.substring(start, curr + 1);
                    if(tmp.length() <= str.length()) {
                        str = new String(tmp);
                        found = true;
                    }
                    
                    res.put(source.charAt(start), res.get(source.charAt(start)) + 1);
                    rest++;
                    start += 1;
                }
            } 
            curr += 1;
        }
        return found ? str : "";
    }
}