2015年6月10日星期三

[LeetCode] Minimum Window Substring

Problem:

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Java Code:

public class Solution {
    public String minWindow(String S, String T) {
        String result = "";
        if (S == null || S.length() == 0 || T == null || T.length() == 0) {
            return result;
        }
        
        Map<Character, Integer> toFind = new HashMap<Character, Integer>();
        for (int i = 0; i < T.length(); i++) {
            if (toFind.containsKey(T.charAt(i))) {
                toFind.put(T.charAt(i), toFind.get(T.charAt(i)) + 1);
            } else {
                toFind.put(T.charAt(i), 1);
            }
        }
        
        Map<Character, Integer> found = new HashMap<Character, Integer>();
        int tCount = 0;
        int leftBound = 0;
        
        for (int i = 0; i < S.length(); i++) {
            char current = S.charAt(i);
            if (!toFind.containsKey(current)) {
                continue;
            }
            if (found.containsKey(current)) {
                found.put(current, found.get(current) + 1);
            } else {
                found.put(current, 1);
            }
            if (found.get(current) <= toFind.get(current)) {
                tCount++;
            }
            if (tCount == T.length()) {
                while (leftBound < S.length()) {
                    char current2 = S.charAt(leftBound);
                    if (!toFind.containsKey(current2)) {
                        leftBound++;
                        continue;
                    }
                    if (found.get(current2) > toFind.get(current2)) {
                        leftBound++;
                        found.put(current2, found.get(current2) - 1);
                        continue;
                    }
                    break;
                }
                if (result.equals("") || S.substring(leftBound, i + 1).length() < result.length()) {
                    result = S.substring(leftBound, i + 1);
                }
            }
        }
        
        return result;
    }
}

没有评论:

发表评论