leetcode76_最小窗口字符串

本文主要是介绍leetcode76_最小窗口字符串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

public String minWindow(String s, String t) {
    // 穷尽每个字符，看是否含有这个子字符串
    // 枚举所有子串，并放入
    // 从字串出发，用双指针枚举->
    Map<Character, Integer> smap = new HashMap<>();
    Map<Character, Integer> tmap = new HashMap<>();
    int m = s.length(), n = t.length();
    for(char c: t.toCharArray()) {
        tmap.put(c, tmap.getOrDefault(c, 0)+1);
    }
    int l = -1, r = 0;    // 一开始是l=0, r=1，但是因为首字符没有进入循环，所以改成了这样
    String ans = s + s; // 需要注意""
    while(l < r && r < m) {

        while(!isValid(smap, tmap) && r < m) {
            Character c = s.charAt(r);
            smap.put(c, smap.getOrDefault(c, 0)+1);
            r++;
        }
        // 如果合理了
        while(l < r && isValid(smap, tmap)) {
            String _ans = s.substring(l+1, r);    // 因为l初始值为-1，所以只能改成这样，也太丑陋了
            if(_ans.length() < ans.length()) ans = _ans;
            Character leftChar = s.charAt(l+1);    // 因为l初始值为-1，所以只能改成这样，也太丑陋了
            smap.put(leftChar, smap.get(leftChar)-1);
            l++;
        }
    }
    if(ans.length() > m) return "";
    else return ans;
}

public boolean isValid(Map<Character, Integer> smap, Map<Character, Integer> tmap) {
    for(Character c: tmap.keySet()) {
        if(!smap.containsKey(c)) return false;
        else {
            if (smap.get(c) < tmap.get(c)) return false;
        }
    }
    return true;
}

这篇关于leetcode76_最小窗口字符串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！