LeetCode.76 最小覆盖子串

问题描述

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

注意：

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

解题思路

1. 初始化: 创建两个计数器或哈希表，一个用于 t 中的字符计数（t_count），一个用于当前窗口中的字符计数（window_count）。定义两个指针，left 和 right，表示窗口的左右边界。还需要定义 have（当前窗口满足 t 需求的字符种类数）和 need（t 中总共需要的不同字符种类数）。

2. 扩大窗口: 移动 right 指针扩大窗口，直到窗口包含了 t 的所有字符。

3. 收缩窗口: 一旦窗口满足条件（即包含了 t 的所有字符），尝试通过移动 left 指针来缩小窗口，直到窗口不再满足条件。在此过程中，记录可能的最小窗口。

4. 更新最小窗口: 在移动 left 指针的同时，检查当前窗口的大小，如果当前窗口的大小比已知的最小窗口小，更新最小窗口。

5. 重复: 重复步骤 2 和 3 直到 right 指针到达 s 的末尾。

6. 提取结果: 根据记录的最小窗口的位置和大小，返回最小覆盖子串。如果没有找到有效的子串，返回空字符串。

关键点

• 滑动窗口: 利用两个指针 left 和 right 追踪当前考虑的 s 的子串。
• 动态调整: 根据 t 的需求动态增加或减少窗口大小。
• 效率: 通过只让每个指针最多遍历 s 一次来保持高效率。
• 字符计数: 使用哈希表对字符进行计数，以便快速检查窗口是否满足条件。

代码实现

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.size() < t.size())
            return "";

        // 统计 t 中各字符的数量
        unordered_map<char, int> t_count;
        for (char c : t)
            t_count[c]++;

        // 滑动窗口内各字符的数量
        unordered_map<char, int> window_count;
        int have = 0;              // 当前窗口中包含了 t 的哪些字符
        int need = t_count.size(); // t 中有多少不同字符需要被包含

        int left = 0;  // 窗口左边界
        int right = 0; // 窗口右边界
        int min_length = INT_MAX;
        int min_left = 0; // 最小窗口的左边界索引

        while (right < s.size()) {
            char c = s[right];
            if (t_count.count(c)) {
                window_count[c]++;
                if (window_count[c] == t_count[c])
                    have++;
            }

            // 当前窗口已经包含了 t 中的所有字符
            while (have == need) {
                // 更新最小窗口
                if (right - left + 1 < min_length) {
                    min_length = right - left + 1;
                    min_left = left;
                }

                // 开始缩小窗口
                char left_char = s[left];
                if (t_count.count(left_char)) {
                    window_count[left_char]--;
                    if (window_count[left_char] < t_count[left_char])
                        have--;
                }
                left++;
            }

            right++;
        }

        return min_length == INT_MAX ? "" : s.substr(min_left, min_length);
    }
};

原文地址：https://blog.csdn.net/LeoLei8060/article/details/140071456

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！