LeetCode 76: 最小覆盖子串

本题是Leetcode hot100字符串专题的最后一题，难度为hard。

问题描述

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

示例

输入: [0,1,0,3,12] 输出: [1,3,12,0,0]

注意：

  • 必须在原数组上操作，不能拷贝额外的数组。
  • 尽量减少操作次数。

注意：

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

示例 1：

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

示例 2：

1
2
3
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

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

思路分析

解决这个问题，想到字符串哈希肯定是不难的。但是对于初学算法的人来说，滑动窗口并不算是一个很好接受、容易想起的技巧。但如果遇到像计算子串最小长度这样的问题，那么滑动窗口应该是备选方法中优先级比较高的一种做法：

  • 窗口的右边界先动，先达到窗口内的字符串满足题目要求的目的。
  • 窗口的左边界后动，在保证窗口满足题目的情况下收缩，确定最小的窗口长度

这种方式并不是最优，但本文只讨论未优化的版本（因为我也没优化到比较好的复杂度）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
		// ori记录字符串t中各字符出现过的次数，cnt记录滑动窗口中字符出现的次数
    unordered_map<char, int> ori, cnt;

		// check函数实现检查，对目标字符串t中的每一个字符，判断滑动窗口中的该字符个数是否足够
		// 不满足说明当前窗口还不满足，窗口右边界还得继续向后走
		// 都满足说明当前窗口满足题目要求，左边界可以继续收缩
    bool check() {
        for (const auto &p: ori) {
            if (cnt[p.first] < p.second) {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t) {
		    // 遍历目标字符串，将每一个字符出现的次数记录在哈希表ori中
        for (const auto &c: t) {
            ++ori[c];
        }

				// 设置左边界为0， 右边界为-1的原因是下面的代码写了++r，如果用r++那么这里为0即可
        int l = 0, r = -1;
        // 将长度设置为int的最大值，INT_MAX是个宏，ansL是最终收缩到最小时候的左边界
        int len = INT_MAX, ansL = -1;

				// s.size()会返回ssize_t类型，无符号整数和int作比较可能在某些编译器报错，所以强转一下
				// 当滑动窗口的右边界r没有达到字符串s结束位置
        while (r < int(s.size())) {
		        // 这个用法在哈希表相关的博文中已经写过，不在此赘述
		        // 只要右边界扫描到的字符在t中出现过，就让右边界向右扩张，同时让cnt记录当前字符
            if (ori.find(s[++r]) != ori.end()) {
                ++cnt[s[r]];
            }
						
						// 一旦check函数确认了窗口满足题目条件，就会执行这段循环
						// 这段循环就是用来收缩窗口的
            while (l <= r && check()) {
		        // 只要新窗口长度：r-l+1比当前窗口长度len小，就更新当前窗口长度
               if (r - l + 1 < len) {
                    len = r - l + 1;
                    ansL = l;
               } 
               // 请明白这个if是在check合法的情况下执行
               // 如果左边界的值是目标字符，那么收缩之后就要在cnt中将其数值-1
	             // 然后再将左边界右移1进行窗口的收缩
               if (ori.find(s[l]) != ori.end()) {
                    --cnt[s[l]];
               }
               ++l;
            }
        }
        // 如果左边界没动过，说明没有答案，返回空串
        // 否则返回这个窗口代表的子串
        return ansL == -1 ? string() : s.substr(ansL, len);
    }
};

复杂度分析

  • 时间复杂度：O(C⋅∣s∣+∣t∣)，其中 n 是数组长度。我们只需要遍历一次数组。
  • 空间复杂度：O(C)。我们只使用了常数级别的额外空间。
  • C是字符集大小，根据字符集大小，时间复杂度呈线性增长

结论

这题的难点并不在字符串哈希，而在对滑动窗口的掌握上，如果看完本题的题解对滑动窗口还是云山雾罩的感觉，可以多找几道类似的题来练。