C语言算法-解答最小覆盖子串问题的C语言实现

题目:

给你一个字符串 s、一个字符串 t，请在字符串 s 里面找出：包含 t 所有字符的最小子串。如果 s 中不存在符合条件的子串，返回空字符串 ""。

说明:

• 如果 s 中不存在符合条件的子串，返回空字符串 ""。
• 保证 t 中字符的重复次数在 s 中不会超过 1000。

引言:

最小覆盖子串问题要求在给定字符串 s 中找到包含字符串 t 所有字符的最小子串。本文将使用 C 语言来解答这个算法问题，并给出 C 代码实现。我们会详细介绍算法思路，并进行代码实现、算法分析、示例和测试、总结。

算法思路:

为了解决最小覆盖子串问题，我们可以使用滑动窗口算法。滑动窗口算法通过维护一个窗口，来在字符串中寻找符合条件的子串。

具体算法步骤如下：

1. 初始化两个指针 left 和 right，分别表示窗口的左边界和右边界，初始化变量 minLen 为一个足够大的值，用于记录最小子串的长度。
2. 初始化两个哈希表 targetMap 和 windowMap，用于记录字符串 t 中字符的出现次数和窗口内字符的出现次数。
3. 遍历字符串 t，将字符及其出现次数存入 targetMap。

4. 使用指针right遍历字符串s，对于每个字符：

   • 将该字符及其出现次数存入 windowMap。
   • 如果 windowMap 包含了 targetMap 中的所有字符，并且窗口内字符的出现次数满足条件，即 windowMap 中每个字符的出现次数都不小于 targetMap 中的出现次数，就将 left 指针向右移动，缩小窗口大小。
   • 在每次移动窗口后，检查当前窗口的长度是否小于 minLen，如果是，则更新 minLen 和 result。
5. 重复步骤4直到 right 指针遍历完整个字符串 s。
6. 返回 result，即最小覆盖子串。

代码实现:

char* minWindow(char* s, char* t) {
    int sLen = strlen(s);
    int tLen = strlen(t);

    if (sLen < tLen) {
        return "";
    }

    // 初始化 targetMap 和 windowMap
    int targetMap[128] = {0}; // ASCII 码字符，最大 128 个
    int windowMap[128] = {0};

    // 遍历字符串 t，将字符及其出现次数存入 targetMap
    for (int i = 0; i < tLen; i++) {
        targetMap[t[i]]++;
    }

    int left = 0;
    int right = 0;
    int minLen = INT_MAX;
    char* result = "";
    int count = 0; // 记录窗口内满足条件的字符个数

    while (right < sLen) {
        // 处理右指针指向的字符
        if (targetMap[s[right]] > 0) {
            windowMap[s[right]]++;
            if (windowMap[s[right]] <= targetMap[s[right]]) {
                count++;
            }
        }

        // 如果窗口内包含了字符串 t 的所有字符
        while (count == tLen) {
            // 更新最小子串
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                result = s + left;
            }

            // 处理左指针指向的字符
            if (targetMap[s[left]] > 0) {
                windowMap[s[left]]--;
                if (windowMap[s[left]] < targetMap[s[left]]) {
                    count--;
                }
            }

            left++;
        }

        right++;
    }

    return minLen == INT_MAX ? "" : strndup(result, minLen);
}

算法分析:

1. 时间复杂度：算法的时间复杂度为 O(sLen + tLen)，其中 sLen 和 tLen 分别是字符串 s 和 t 的长度。
2. 空间复杂度：算法的空间复杂度为 O(1)，因为哈希表的大小是固定的，不随输入数据的大小而变化。

示例和测试:

示例1:

输入: s = "ADOBECODEBANC", t = "ABC"
输出: "BANC"

示例2:

输入: s = "a", t = "a"
输出: "a"

总结:

通过使用滑动窗口算法，我们用 C 语言实现了解决最小覆盖子串问题的代码。这个算法能够高效地在字符串 s 中找到包含字符串 t 所有字符的最小子串。希望本文能够帮助你理解解决这个算法问题的思路和方法。