[leetcode] 76. 最小覆盖子串

痛定思痛。 2021-09-29 12:58 245阅读 0赞

[76. 最小覆盖子串][76.]

脑子不清醒的时候，  
不要刷题，不要刷题，不要刷题。。。。

我这么困，为什么要刷题！

在串S上维护i，j两个指针，i表示当前包含T所有字母的起始位置，相反j是终止位置。

首先让j一直加，直到找到了字串s.substring(i,j)满足条件。之后，j再++，每碰到一个T中拥有的字母，我们就尝试将i++，直到i不能再加了为止。

class Solution {
        public String minWindow(String s, String t) {
            if (t.length() > s.length()) {
                return "";
            }
            Map<Character, Integer> tmap = new HashMap<>();
            Map<Character, Integer> smap = new HashMap<>();
            for (int i = 0; i < t.length(); i++) {
                tmap.putIfAbsent(t.charAt(i), 0);
                tmap.put(t.charAt(i), tmap.get(t.charAt(i)) + 1);
            }
    
            int i = 0, j = 0, k = -1;
            int ansi = 0, ansk = Integer.MAX_VALUE;
            while (j < s.length()) {
                smap.putIfAbsent(s.charAt(j), 0);
                smap.put(s.charAt(j), smap.get(s.charAt(j)) + 1);
                if (tmap.containsKey(s.charAt(j))) {
                    k = j;
                    if (ok(smap, tmap)) {
                        while (!tmap.containsKey(s.charAt(i)) || smap.get(s.charAt(i)) > tmap.get(s.charAt(i))) {
                            // rm i
                            smap.put(s.charAt(i), smap.get(s.charAt(i)) - 1);
                            if (smap.get(s.charAt(i)) == 0) {
                                smap.remove(s.charAt(i));
                            }
                            i++;
                        }
                        if (k - i < ansk - ansi) {
                            ansi = i;
                            ansk = k;
                        }
                    }
                }
                j++;
            }
    
            if (ansk == Integer.MAX_VALUE) {
                return "";
            }
            return s.substring(ansi, ansk + 1);
        }
    
        private boolean ok(Map<Character, Integer> smap, Map<Character, Integer> tmap) {
            for (Map.Entry<Character, Integer> entry : tmap.entrySet()) {
                if (smap.get(entry.getKey()) == null || (entry.getValue() > smap.get(entry.getKey()))) {
                    return false;
                }
            }
            return true;
        }
    }

转载于:https://www.cnblogs.com/acbingo/p/9388329.html

[76.]: https://leetcode-cn.com/problems/minimum-window-substring/description/