最短包含字符串的长度

[编程题]最短包含字符串的长度

热度指数：2120 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定字符串str1和str2，求str1的字串中含有str2所有字符的最小字符串长度。

输入描述:

输入包括两行，第一行一个字符串，代表str1，第二行也是一个字符串，代表str2。

输出描述:

输出str1的字串中含有str2所有字符的最小字符串长度，如果不存在请输出0。

示例1

输入

abcde
ac

输出

说明

“abc”中包含“ac”，且“abc”是所有满足条件中最小的。

示例2

输入

12345
344

输出

算法知识视频讲解

helloxuanbao

#include <stdio.h>
#include <string.h>
#include <limits.h>

#define MIN(X, Y) ((X) < (Y) ? (X) : (Y))
#define MAX_LEN 100001

int min_len(char *str1, char *str2);

int main(void) {
    char str1[MAX_LEN], str2[MAX_LEN];
    scanf("%s%s", str1, str2);
    printf("%d\n", min_len(str1, str2));
    return 0;
}

int min_len(char *str1, char *str2) {
    int len1 = (int) strlen(str1);
    int len2 = (int) strlen(str2);
    int map[256];
    memset(map, 0, sizeof(int) * 256);
    for (int i = 0; i < len2; i++) {
        map[str2[i]]++;
    }

    int min_len = INT_MAX, need = len2;
    int l = 0, r = -1;
    while (++r < len1) {
        map[str1[r]]--;
        if (map[str1[r]] >= 0) need--;
        if (need == 0) {
            while (map[str1[l]] < 0) {
                map[str1[l++]]++;
            }
            min_len = MIN(min_len, r - l + 1);
        }
    }
    return min_len != INT_MAX ? min_len : 0;
}

发表于 2022-02-11 22:24:43 回复(0)