JAVA---------------Easy Version To Understand!!!!


  • -1
    H
    	public static String minWindow(String s, String t) {
    	if (s == null || t == null || s.length() == 0 || t.length() == 0)
    		return "";
    	HashMap<Character, Integer> needFind = new HashMap<Character, Integer>();/
    	HashMap<Character, Integer> hasFind = new HashMap<Character, Integer>();//
    	for (int i = 0; i < t.length(); i++) {
    		if (needFind.get(t.charAt(i)) == null)
    			needFind.put(t.charAt(i), 1);
    		else
    			needFind.put(t.charAt(i), needFind.get(t.charAt(i)) + 1);
    	}
    	int low = 0, high = 0, minLen = Integer.MAX_VALUE, begin = -1, end = 0, count = 0;// 
    	while (high < s.length()) {
    		if (needFind.get(s.charAt(high)) != null) {
    			if (hasFind.get(s.charAt(high)) == null) {
    				hasFind.put(s.charAt(high), 1);
    				count++;
    			} else {
    				hasFind.put(s.charAt(high), hasFind.get(s.charAt(high)) + 1);
    				if (hasFind.get(s.charAt(high)) <= needFind.get(s.charAt(high)))
    					count++;
    			}
    			if (count == t.length()) {// 
    				while (needFind.get(s.charAt(low)) == null
    						|| hasFind.get(s.charAt(low)) > needFind.get(s.charAt(low))) {
    					if (needFind.get(s.charAt(low)) != null
    							&& hasFind.get(s.charAt(low)) > needFind.get(s.charAt(low)))
    						hasFind.put(s.charAt(low), hasFind.get(s.charAt(low)) - 1);
    					low++;
    				}
    				if (high - low + 1 < minLen) {
    					minLen = high - low + 1;
    					begin = low;
    					end = high;
    				}
    
    			}
    		}
    		high++;
    	}
    	if (begin == -1)// 
    		return "";
    	return s.substring(begin, end + 1);
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.