LeetCode 面试经典150题 [32/150 最小覆盖子串]

题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

 复制代码
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

 复制代码
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

 复制代码
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

个人C++解答

 复制代码
class Solution {
public:
    string minWindow(string s, string t) {
        if (s.size() < t.size())
            return "";
        if (s.size() == 1 && t.size() == 1) {
            if (s.compare(t) == 0)
                return s;
            else
                return "";
        }
        unordered_map<char, int> myMap;
        for (char w : t) myMap[w]++;
        int left = 0, right = 0;
        bool first = true,find_one = false;
        string result = s;
        string TempStr = "";
        unordered_map TempMap(myMap);
        while (right < s.size()) {
            if (first) {
                if (myMap.find(s[right]) != myMap.end()){
                    find_one = true;
                    TempMap[s[right]]--;
                }
                TempStr.push_back(s[right]);
                if (TempMap[s[right]] <= 0)
                    TempMap.erase(s[right]);
            } else {
                TempStr.push_back(s[right]);
                if (s[right] == s[left - 1]) {
                    TempMap.clear();
                }
            }
            if (TempMap.empty()) {
                result = TempStr.size() <= result.size() ? TempStr : result;
                first = false;
                for (int i = left; i <= right; i++) {
                    if (myMap.find(s[i]) != myMap.end()) {
                        TempMap[s[i]]++;
                    }
                }
                while (left < right) {
                    if (myMap.find(s[left]) != myMap.end()) {
                        TempMap[s[left]]--;
                        if (TempMap[s[left]] < myMap[s[left]])
                            break;
                    }
                    left++;
                    TempStr = TempStr.substr(1);
                }
                left++;
                if (TempStr.size() >= t.size())
                    result = TempStr.size() <= result.size() ? TempStr : result;
                TempStr = TempStr.substr(1);
            }
            right++;
        }
        if(first&&!TempMap.empty())
            return "";
        return result=find_one==true ?result:"";
        
    }
};

GPT优化

 复制代码
class Solution {
public:
    string minWindow(string s, string t) {
        // Edge case: If s is shorter than t, it's impossible to have a valid window
        if (s.size() < t.size())
            return "";
 
        // Count the frequency of characters in t
        unordered_map<char, int> t_count;
        for (char c : t) {
            t_count[c]++;
        }
 
        // Sliding window variables
        unordered_map<char, int> window_count;
        int have = 0, need = t_count.size(); // have: number of characters meeting the requirement
        int left = 0, right = 0;
        int min_length = INT_MAX, min_left = 0;
 
        // Expand the window by moving the right pointer
        while (right < s.size()) {
            char c = s[right];
            window_count[c]++;
            if (t_count.find(c) != t_count.end() && window_count[c] == t_count[c]) {
                have++;
            }
 
            // Contract the window by moving the left pointer
            while (have == need) {
                // Update the minimum window
                if (right - left + 1 < min_length) {
                    min_length = right - left + 1;
                    min_left = left;
                }
 
                // Remove the leftmost character from the window
                window_count[s[left]]--;
                if (t_count.find(s[left]) != t_count.end() && window_count[s[left]] < t_count[s[left]]) {
                    have--;
                }
                left++;
            }
            right++;
        }
 
        // If no valid window was found, return an empty string
        if (min_length == INT_MAX) {
            return "";
        }
 
        return s.substr(min_left, min_length);
    }
};