76. 最小覆盖子串。优化官方题解!

2023-12-21 14:57:47

leetcode原题如下:

????????

????????给你一个字符串?s?、一个字符串?t?。返回?s?中涵盖?t?所有字符的最小子串。如果?s?中不存在涵盖?t?所有字符的子串,则返回空字符串?""?。

注意:

  • 对于?t?中重复字符,我们寻找的子字符串中该字符数量必须不少于?t?中该字符数量。
  • 如果?s?中存在这样的子串,我们保证它是唯一的答案。

????????

解题思路---滑动窗口

如何判断当前的窗口包含所有 t 所需的字符呢?我们可以用一个哈希表表示 t 中所有的字符以及它们的个数,用一个哈希表动态维护窗口中所有的字符以及它们的个数,如果这个动态表中包含 t 的哈希表中的所有字符,并且对应的个数都不小于 t 的哈希表中各个字符的个数,那么当前的窗口是「可行」的。

官方题解:

    Map<Character, Integer> ori = new HashMap<Character, Integer>();
    Map<Character, Integer> cnt = new HashMap<Character, Integer>();

    public String minWindow(String s, String t) {
            Map<Character, Integer> ori = new HashMap<>();
        Map<Character, Integer> cnt = new HashMap<>();

        // 预处理,初始化 ori 表
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }

        int l = 0, r = 0;
        int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
        int sLen = s.length();
        int required = ori.size();  // 需要匹配的字符种类数量
        int formed = 0;  // 已经匹配的字符种类数量

        while (r < sLen) {
            char c = s.charAt(r);
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);

            if (ori.containsKey(c) && cnt.get(c).equals(ori.get(c))) {
                formed++;
            }

            while (formed == required && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }

                char leftChar = s.charAt(l);
                cnt.put(leftChar, cnt.get(leftChar) - 1);

                if (ori.containsKey(leftChar) && cnt.get(leftChar) < ori.get(leftChar)) {
                    formed--;
                }

                l++;
            }

            r++;
        }

        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }

注意:这里 t 中可能出现重复的字符,所以我们要记录字符的个数。

考虑如何优化? 如果 s=XX?XABCXXXX,t=ABC,那么显然 [XX?XABC]是第一个得到的「可行」区间,得到这个可行区间后,我们按照「收缩」窗口的原则更新左边界,得到最小区间。我们其实做了一些无用的操作,就是更新右边界的时候「延伸」进了很多无用的 X,更新左边界的时候「收缩」扔掉了这些无用的 X,做了这么多无用的操作,只是为了得到短短的 ABC。没错,其实在 s 中,有的字符我们是不关心的,我们只关心 t中出现的字符,我们可不可以先预处理 s,扔掉那些 t?中没有出现的字符,然后再做滑动窗口呢?也许你会说,这样可能出现 XXABXXC的情况,在统计长度的时候可以扔掉前两个 X,但是不扔掉中间的 X,怎样解决这个问题呢?优化后的时空复杂度又是多少?代码给出优化的版本.

public class MinimumWindowSubstring {
    public String minWindow(String s, String t) {
        // 用于记录 t 中各字符需要匹配的次数
        Map<Character, Integer> ori = new HashMap<>();

        // 用于记录当前窗口中各字符已匹配的次数
        Map<Character, Integer> cnt = new HashMap<>();

        // 预处理,初始化 ori 表
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }

        int l = 0, r = 0; // 窗口的左右边界
        int len = Integer.MAX_VALUE; // 记录当前最小窗口的长度
        int ansL = -1, ansR = -1; // 记录当前最小窗口的左右边界
        int sLen = s.length(); // 字符串 s 的长度

        int required = ori.size(); // 需要匹配的字符种类数量
        int formed = 0; // 已经匹配的字符种类数量

        // 右指针滑动
        while (r < sLen) {
            char c = s.charAt(r);
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);

            // 如果当前字符在 ori 表中,并且已匹配次数等于 ori 表中的次数,增加已匹配字符种类数量
            if (ori.containsKey(c) && cnt.get(c).equals(ori.get(c))) {
                formed++;
            }

            // 左指针滑动,窗口收缩
            while (formed == required && l <= r) {
                // 更新最小窗口的长度和边界
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
                    ansR = l + len;
                }

                // 移动左指针,减少已匹配字符的次数
                char leftChar = s.charAt(l);
                cnt.put(leftChar, cnt.get(leftChar) - 1);

                // 如果左边界字符在 ori 表中,并且减少后的次数小于 ori 表中的次数,减少已匹配字符种类数量
                if (ori.containsKey(leftChar) && cnt.get(leftChar) < ori.get(leftChar)) {
                    formed--;
                }

                l++;
            }

            // 右指针继续滑动
            r++;
        }

        // 返回最小窗口对应的子串
        return ansL == -1 ? "" : s.substring(ansL, ansR);
    }
}

这段代码中的核心思想是使用滑动窗口来找到包含字符串 t 中所有字符的最小窗口。下面是代码中各部分的解释:

  1. oricnt 的初始化:

    • ori 表用于记录字符串 t 中各字符需要匹配的次数。
    • cnt 表用于记录当前窗口中各字符已匹配的次数。
  2. 预处理,初始化 ori 表:

    • 遍历字符串 t,将其中各字符及其需要匹配的次数记录在 ori 表中。
  3. 窗口的左右边界 lr

    • 使用两个指针 lr 来确定窗口。
  4. requiredformed

    • required 记录需要匹配的字符种类数量,即 ori 表的大小。
    • formed 记录已经匹配的字符种类数量,初始为 0。
  5. 右指针滑动(while (r < sLen)):

    • 不断移动右指针 r,直到窗口包含了字符串 s 中的所有字符。
  6. 左指针滑动,窗口收缩(while (formed == required && l <= r)):

    • 移动左指针 l,尝试缩小窗口的大小。
    • 更新最小窗口的长度和边界。
  7. 左右指针继续滑动,直至右指针到达字符串末尾:

文章来源:https://blog.csdn.net/qq_28909387/article/details/135127304
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。