[leetcode] Minimum Window Substring

Posted by: lexigrey on: November 18, 2013

• In: leetcode
• 2 Comments

还是两个map，一个want, 一个has，i指当前window的开头，j指结尾；want满足了的时候就试试能不能从i处删点什么。写了25分钟然后各种debugger，这题还得重做。

public String minWindow(String S, String T) {
    Map<Character, Integer> has = new HashMap<Character, Integer>();
    Map<Character, Integer> want = new HashMap<Character, Integer>();
    String res = S + S;
    char[] s = S.toCharArray();
    char[] t = T.toCharArray();
    for (int i = 0; i < t.length; i++) {
        want.put(t[i], want.get(t[i]) == null ? 1 : want.get(t[i]) + 1);
        has.put(t[i], 0);
    }
    int i = 0;
    for (int j = i; j < s.length; j++) {
        if (want.containsKey(s[j])) {
            has.put(s[j], has.get(s[j]) + 1);
            if (satisfy(has, want)) {// satisfies everything nows, try move i
                while (!want.containsKey(s[i]) || has.get(s[i]) > want.get(s[i])) { //move i until not movable
                    if (want.containsKey(s[i]) && has.get(s[i]) > want.get(s[i]))
                        has.put(s[i], has.get(s[i]) - 1); 
                    i++;
                }
                String currWindow = S.substring(i, j + 1);
                res = res.length() > currWindow.length() ? currWindow : res;
            }
        }
    }
    return res.length() > S.length() ? "" : res;
}
private boolean satisfy( Map<Character, Integer> has, Map<Character, Integer> want) {
    for (Character c : want.keySet()) {
        if (has.get(c) < want.get(c))
            return false;
    }
    return true;
}

Advertisements

Tags: hard, map