Leetcode76. Minimal Covering Substring

题目传送地址： https://leetcode.cn/problems/minimum-window-substring/

运行效率

代码如下：

class Solution {
    
//滑动窗口解法 In order to enhance the contrast of two strings efficiency, 于是用了map,Dynamic maintenance of sliding windowmap
  public static String minWindow(String s, String t) {
    
        //处理边界情况
        if ("".equals(s)) {
    
            return "";
        }
        if (s.length() == 1) {
    
            if (s.equals(t)) {
    
                return s;
            }
            return "";
        }
        String result = "";
        //Maintain a dynamic sliding windowMap,Identifies the window in the number of occurrences of each characters
        Map<Character, Integer> tMap = getTmap(t);
        Map<Character, Integer> sMap = new HashMap<>();
        //滑动窗口
        int left = 0; //滑动窗口的左指针
        int right = 0;  //Sliding window right pointer
        sMap.put(s.charAt(0), 1);
        while (right < s.length()) {
    
            if (right - left + 1 < t.length()) {
    
                right++;
                if (right < s.length()) {
    
                    putValToMap(s.charAt(right), sMap);
                }
                continue;
            }
            Character character = vaildStr(sMap, tMap);
            if (character == null) {
      //如果验证通过
                String substring = s.substring(left, right + 1);
                if ("".equals(result)) {
    
                    result = substring;
                } else {
    
                    if (substring.length() < result.length()) {
    
                        result = substring;
                    }
                }
                deleteValToMap(s.charAt(left), sMap); //Start with the sliding windowmap里删除,And then the left pointer moves to the right,Don't make the order
                left++;
            } else {
    
                right++;
                if (right < s.length()) {
    
                    putValToMap(s.charAt(right), sMap);
                }
                while (right < s.length()) {
    
                    char c = s.charAt(right);
                    if (c == character) {
    
                        break;
                    }
                    right++;
                    if (right < s.length()) {
    
                        putValToMap(s.charAt(right), sMap);
                    }
                }
            }
            if (result.length() == t.length()) {
    
                return result;
            }
        }
        return result;
    }

    public static void putValToMap(Character c, Map<Character, Integer> map) {
    
        if (map.containsKey(c)) {
    
            map.put(c, map.get(c) + 1);
        } else {
    
            map.put(c, 1);
        }
    }

    public static void deleteValToMap(Character c, Map<Character, Integer> map) {
    
        if (map.containsKey(c)) {
    
            Integer count = map.get(c);
            if (count == 1) {
    
                map.remove(c);
            } else {
    
                map.put(c, count - 1);
            }
        }
    }

    public static Map<Character, Integer> getTmap(String t) {
    
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
    
            char c = t.charAt(i);
            if (map.containsKey(c)) {
    
                Integer count = map.get(c);
                map.put(c, count + 1);
            } else {
    
                map.put(c, 1);
            }
        }
        return map;
    }

    /** * Validate elements within a sliding window, whether they contain all the elements of the target object * @param sMap * @param tMap * @return Returns the missing elements */
    public static Character vaildStr(Map<Character, Integer> sMap, Map<Character, Integer> tMap) {
    
        Iterator<Character> iterator = tMap.keySet().iterator();
        while (iterator.hasNext()) {
    
            Character c = iterator.next();
            Integer tCount = tMap.get(c);
            if (sMap.containsKey(c)) {
    
                Integer sCount = sMap.get(c);
                if (sCount < tCount) {
    
                    return c;
                }
            } else {
    
                return c;
            }
        }
        return null;
    }
}