跳转至

76. 最小覆盖子串

最后更新：2024-05-10-22

链接：https://leetcode.cn/problems/minimum-window-substring/description/

题目描述

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

注意：

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

题目示例

输入： s = "ADOBECODEBANC", t = "ABC"

输出： "BANC"

解释： 最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'

输入： s = "a", t = "a"

输出： "a"

解释： 整个字符串 s 是最小覆盖子串

输入： s = "a", t = "aa"

输出： ""

解释： t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

提示：

  • \(m == s.length\)
  • \(n == t.length\)
  • \(1 <= m, n <= 10^5\)
  • s 和 t 由英文字母组成

进阶

你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

解题思路

使用滑窗思想，在判断上做优化

最先的时候使用滑窗算法做的，跟官方的方法一样，每次都是去判断得到的子串是否是满足条件的最小子串，判断的方法就是比较：

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
bool checkInclude(const char * t, const int *count_s, const int *count_t)
{
    int len_t = (int)strlen(t);

    for (int i = 0; i < len_t; i++) {
        if (count_t[t[i]] > count_s[t[i]]) {
            return false;
        }
    }

    return true;
}

这是一个很笨的办法，题是做出来了，只是最后一个用例超时了。因此，想了各种的优化。。。。。

后来，看了其他同学的题解，有下面这么一个优化算法，大概思想如下：

  • T字符串中，所有字符的个数就是T字符串的长度；
  • 我们从S字符串中找到在T字符串中出现的字符，然后计数，遇到计数超过T的就跳过当次的，最后当计数值=len(T)的时候，就找到了我们需要的子串。

这样描述可能不太好理解，我们举个例子：

输入： AAAAAABBBBBBCCCCCC ABC

  • 对于这个数据，我们从开头计数，遇到第一个A,计数sum_s + 1, count_s['A']++;
  • 继续，遇到第二个A的时候，因为count_s['A'] >= count_T['A'],我们不对第二个A计数，sum_s保持不变，继续往后；
  • 同样的，对第一个B计数，后面的B不计数，第一个B的时候，sum_s + 1；然后遇到第一个C的时候，sum_s +1；
  • 这个时候，sum_s = 3， 刚好=len(T)

再看看我们取到的子串AAAAAABBBBBBC， 刚好是满足条件的一个子串。

然后对于这个子串，我们再从左侧开始，删除count_s['A'] > count_t['A']的部分，使得count_s['A'] = count_t['A']，得到子串ABBBBBBC，这就是我们得到的一个满足条件的子串，依次类推，直到我们找到最小的那个。

以题目示例为例：

  • 输入：ADOBECODEBANC ABC
  • 第一轮，我们找到ADOBEC；
  • 第二轮，我们找到DOBECODEBA， 然后去掉左侧的无效字符，得到CODEBA；
  • 第三轮，我们找到BANC， 两边都没有要去掉的，然后看长度，这个就是我们需要的最小值。
C
 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#define MAX_CHAR_NUM 255

void getSlidingWindows(const char *left, const char *right, char *result, int *resultSize, int *maxLen)
{
    int len = (int)(right - left);
    if (*maxLen > len) {
        memset(result, 0, resultSize);
        memcpy(result, left, len);
        *maxLen = len;
        result[*maxLen] = '\0';
    }
}

void deleteSlidingWindowLeftInvalidChar(char **left, int *count_s, const int *count_t)
{
    char *begin = *left;
    while ((count_t[*begin] == 0) || (count_s[*begin] > count_t[*begin])) {
        count_s[*begin]--;
        begin++;
    }

    *left = begin;
}

void moveSlidingWindowRightFrame(char **right, int *count_s, const int *count_t, int *sum_s)
{
    char *end = *right;
    count_s[*end]++;
    if (count_s[*end] <= count_t[*end]) {
        (*sum_s)++;
    }
    end++;
    *right = end;
}

char *minWindow(const char *s, const char *t)
{
    int count_s[MAX_CHAR_NUM] = {0};
    int count_t[MAX_CHAR_NUM] = {0};
    char* result = NULL;
    char *left, *right;
    int len_s = (int)strlen(s);
    int len_t = (int)strlen(t);
    int sum_s = 0;
    int result_l = len_s + 1;

    if (len_t > len_s) {
        return "";
    }

    memset(count_s, 0, sizeof(count_s));
    memset(count_t, 0, sizeof(count_t));

    result = (char*)malloc(len_s + 1);
    if (result == NULL) {
        return "";
    }
    memset(result, 0, len_s + 1);

    for (int i = 0; i < len_t; i++) {
        count_t[t[i]]++;
    }

    // 找到第一个满足条件的子串的end
    left = s;
    right = s;
    while ((left <= right) && (*left != '\0') && (*right != '\0')) {
        // right 向右移动，不在T中的跳过
        if (count_t[*right] == 0) {
            right++;
            continue;
        }

        // right在T中，并且个数不到count_t[*right]， 计数一个,sum_s只记录S字符串中在T字符串出现过的字符个数。
        moveSlidingWindowRightFrame(&right, count_s, count_t, &sum_s);

        // 找到了满足条件的子串，sum_s与T的长度相同时，说明找到了一个满足条件的子串
        if (len_t == sum_s) {
            // 从left开始，删除多余的字符
            deleteSlidingWindowLeftInvalidChar(&left, count_s, count_t);
            getSlidingWindows(left, right, result, len_s + 1, &result_l);

            // 去掉最左侧的一个值，继续
            sum_s--;
            count_s[*left]--;
            left++;
        }

        if (count_t[*left] == 0) {
            left++;
        }
    }

    return result;
}
Go
1