leetcode76：最小覆盖子串

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

/*
    滑动窗口

    使用哈希表，统计出 T 中所有字符出现的次数。
    使用两个指针 i, j(i >= j) 扫描整个字符串，统计 i, j 之间每种字符出现的次数。
    遍历过程中的操作如下：
    1. 加入 s[i]，更新哈希表；
    2. 检查 s[j] 是否多余。若是，则移除 s[j]。
    3. 判断当前窗口是否已经满足 T 中所有字符。若是，则更新答案。

    时间复杂度：O(m + n*C)
        其中 n 为字符串 s 的长度，m 为字符串 t 的长度，C 为字符集的大小。
    空间复杂度：O(C)
        设字符集大小为 C
*/
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hs, ht;
        for (const char& c : t) {
            ht[c] ++;
        }

        string res;
        int cnt = 0;
        for (int i = 0, j = 0; i < s.size(); i ++) {
            // s[i], s[j] 分别是移出、移入窗口的字符
            hs[s[i]] ++;
            if (hs[s[i]] <= ht[s[i]]) cnt ++;
            // 判断左侧窗口是否需要收缩
            while (hs[s[j]] > ht[s[j]]) hs[s[j ++]] --;
            // 窗口内数据的更新
            if (cnt == t.size()) {
                if (res.empty() || res.size() > i - j + 1) {
                    res = s.substr(j, i - j + 1);
                }
            }
        }

        return res;
    }
};

/*
    思路同上，写法不同
*/
class Solution_1 {
public:
    string minWindow(string s, string t) {
        // 使用哈希表，记录 t 中每个字符出现的次数
        unordered_map<char, int> need;
        for (const char& c : t) {
            need[c] ++;
        }

        // 使用哈希表，记录窗口中的字符
        unordered_map<char, int> window;
        // 定义滑动窗口的左右边界
        int left = 0, right = 0;
        // 定义窗口中满足 need 条件的字符个数
        int valid = 0;
        // 最小覆盖子串的起始索引和长度
        int start = 0, len = INT_MAX;

        while (right < s.size()) {
            // c 是将移入窗口的字符
            char c = s[right ++];
            // 窗口内数据进行更新
            if (need.count(c)) {
                window[c] ++;
                if (window[c] == need[c]) {
                    valid ++;
                }
            }
            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d 是将移出窗口的字符
                char d = s[left ++];
                // 窗口内数据进行更新
                if (need.count(d)) {
                    if (window[d] == need[d]) valid --;
                    window[d] --;
                }
            }
        }

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

int main() {
    Solution solution;
    vector<string> s_strs = { "ADOBECODEBANC", "a", "a" };
    vector<string> t_strs = { "ABC", "a", "aa" };
    
    for (int i = 0; i < s_strs.size(); i ++) {
        string s = s_strs[i];
        string t = t_strs[i];
        cout << "Input: s = " << s << ", t = " << t << endl;
        string res = solution.minWindow(s, t);
        cout << "Output: " << (res.empty() ? "null" : res) << endl;
    }
    
    return 0;
}

Golang 代码

package main

import "fmt"

/*
   基本思路：
       1.创建两个字典 need 和 window，分别记录字符串 T 中字符的需求数量和滑动窗口中字符的出现次数。
       2.初始化最小子串的起始位置和长度。
       3.使用双指针 left 和 right 表示滑动窗口的左右边界。
       4.移动 right 指针，将字符添加到 window 中，并更新 window 中字符的出现次数。
       5.当 window 中包含了 T 中的所有字符时，调整 left 指针来收缩窗口，直到窗口不再满足条件。
       6.在收缩窗口的过程中，更新最小子串的起始位置和长度。
       7.重复步骤 4-6，直到 right 指针到达字符串 S 的末尾。

   时间复杂度：O(n)
       其中 n 是字符串 S 的长度。
       right 指针遍历字符串 S，这部分的时间复杂度为 O(n)。
       left 指针可能会移动多次，但最多不会超过 n 次。
   空间复杂度：O(k)
       其中 k 是字符串 T 中不同字符的数量。
       字典的大小，取决于字符串 T 中字符的种类数。
*/
func minWindow(s string, t string) string {
    need := make(map[byte]int)   // need 记录字符串 T 中字符的需求数量
    window := make(map[byte]int) // window 记录滑动窗口中字符的出现次数
    // 统计字符串 t 中字符的出现次数
    for i := 0; i < len(t); i ++ {
        need[t[i]] ++
    }

    start, length := 0, len(s) + 1
    left, right := 0, 0
    // 统计窗口中字符的出现次数
    for  right < len(s) {
        // 窗口内数据进行更新
        if _, ok := need[s[right]]; ok {
            window[s[right]] ++
        }
        // 判断左侧窗口是否要收缩
        for checkWindow(need, window) {
            // 更新最小子串的起始位置和长度
            if right - left + 1 < length {
                start = left
                length = right - left + 1
            }
            // 窗口内数据进行更新
            if _, ok := need[s[left]]; ok {
                window[s[left]] --
            }
            left ++
        }
        right ++
    }

    // 若没找到，则返回空字符串
    if length == len(s) + 1 {
        return ""
    }
    // 返回最小子串
    return s[start : start + length]
}

// 判断窗口中是否包含了字符串 T 中的所有字符
func checkWindow(need map[byte]int, window map[byte]int) bool {
    for k, v := range need {
        if window[k] < v {
            return false
        }
    }

    return true
}

/*
    思路同上，写法不同
*/
func minWindow_1(s string, t string) string {
    need := make(map[byte]int)   // need 记录字符串 T 中字符的需求数量
    window := make(map[byte]int) // window 记录滑动窗口中字符的出现次数
    // 统计字符串 t 中字符的出现次数
    for i := 0; i < len(t); i ++ {
        need[t[i]] ++
    }

    start, length := 0, len(s) + 1
    left, right, valid := 0, 0, 0
    // 统计窗口中字符的出现次数
    for right < len(s) {
        c := s[right]
        right ++
        if _, ok := need[c]; ok {
            window[c] ++
            if window[c] == need[c] {
                valid ++
            }
        }
        for valid == len(need) {
            if right - left < length {
                start = left
                length = right - left
            }
            d := s[left]
            left ++
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid --
                }
                window[d] --
            }
        }
    }

    // 若没找到，则返回空字符串
    if length == len(s) + 1 {
        return ""
    }
    // 返回最小子串
    return s[start : start + length]
}

func main() {
    // 测试用例
	testCases := []struct {
		s        string
		t        string
		expected string
	}{
		{"ADOBECODEBANC", "ABC", "BANC"},
		{"a", "a", "a"},
		{"a", "aa", ""},
	}

	for i, tc := range testCases {
		result := minWindow(tc.s, tc.t)
		fmt.Printf("Test Case %d, Input: s = %q, t = %q\n", i+1, tc.s, tc.t)
		if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %q, PASS\n", i+1, result)
		} else {
			fmt.Printf("Test Case %d, Output: %q, FAIL (Expected: %q)\n", i+1, result, tc.expected)
		}
	}
}