使用C++解决如下问题:给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保证它是唯一的答案。 示例 1: 输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" 解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。 示例 2: 输入:s = "a", t = "a" 输出:"a" 解释:整个字符串 s 是最小覆盖子串。 示例 3: 输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中, 因此没有符合条件的子字符串,返回空字符串。 提示: m == s.length n == t.length 1 <= m, n <= 105 s 和 t 由英文字母组成
时间: 2023-02-24 14:11:25 浏览: 264
C++实现将一个字符串中的字符替换成另一个字符串的方法
以下是使用 C 语言解决该问题的代码:
```
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX_N 100005
int cnt[26];
int map[26];
char* minWindow(char* s, char* t) {
int slen = strlen(s);
int tlen = strlen(t);
memset(cnt, 0, sizeof cnt);
memset(map, 0, sizeof map);
for (int i = 0; i < tlen; i++) {
cnt[t[i] - 'A']++;
}
int start = 0, end = 0, cnt_t = tlen, minLen = MAX_N, minStart = 0;
while (end < slen) {
if (cnt[s[end] - 'A'] > 0) {
cnt_t--;
}
cnt[s[end] - 'A']--;
end++;
while (cnt_t == 0) {
if (end - start < minLen) {
minLen = end - start;
minStart = start;
}
cnt[s[start] - 'A']++;
if (cnt[s[start] - 'A'] > 0) {
cnt_t++;
}
start++;
}
}
if (minLen == MAX_N) {
char* res = (char*)malloc(sizeof(char));
res[0] = '\0';
return res;
}
char* res = (char*)malloc(sizeof(char) * (minLen + 1));
for (int i = 0; i < minLen; i++) {
res[i] = s[minStart + i];
}
res[minLen] = '\0';
return res;
}
int main() {
char s[] = "ADOBECODEBANC";
char t[] = "ABC";
char* res = minWindow(s, t);
printf("%s\n", res);
return 0;
}
```
该代码使用滑动窗口算法解决了该问题,具体思路如下:
1. 初始化:用 cnt 数组统计 t 中每个字符的数量,再用 map 数组统计 s 中每个字符出现的数量。
2. 遍历 s:每遍历到一个字符,就将其出现次数减一,如
阅读全文