超链接网站建设,做资源教程网站,个人建购物网站怎么备案,网站地图做法做题目描述
给定两个字符串 S 和 T#xff0c;求 S 中包含 T 所有字符的最短连续子字符串的长度#xff0c;同时要求时间复杂度不得超过 O(n)。
输入输出样例
输入是两个字符串 S 和 T#xff0c;输出是一个 S 字符串的子串。样例如下#xff1a; 在这个样例中#xff0c…题目描述
给定两个字符串 S 和 T求 S 中包含 T 所有字符的最短连续子字符串的长度同时要求时间复杂度不得超过 O(n)。
输入输出样例
输入是两个字符串 S 和 T输出是一个 S 字符串的子串。样例如下 在这个样例中 S 中同时包含一个 A、一个 B、一个 C 的最短子字符串是“BANC”。
Input: S “ADOBECODEBANC”, T “ABC” Output: “BANC”
算法步骤
本题使用滑动窗口求解即两个指针 l 和 r 都是从最左端向最右端移动且 l 的位置一定在 r 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环但是因为 while 循环负责移动 l 指针且 l 只会从左到右移动一次因此总时间复杂度仍然是 O(n)。先统计 T 中的各字符是否出现及数量用 flag[i]代表代表ACII值为i的字符是否出现 chars [i] 表示ACII值为i的字符在T中出现的次数也可以用于表示当前窗口中缺少的字符的数量。cnt 表示当前窗口中的 包含T中字符 的数量由于后续代码中 cnt 的变化都和 chars 有关每次chars 变化后cnt才变换则可直接用 cnt 的值和 T的大小比较判断滑动窗口中是否都包含了T中的字符。左指针 l 和右指针 r 开始默认指向字符串最左边的第一个元素。初始化滑动窗口的最小值为整个S的长度1即表示整个S字符串都不匹配。接下来的 for 外层循环 负责移动窗口的 右指针r 来遍历字符串 S若 S[r] 不是T中的字符则不做处理 r 往右遍历若 S[r] 是T中的字符则进行以下处理 判断 当前窗口中是否还缺少字符 S[r] 若缺少则 cnt。若 cnt 的值等于 T 的大小则表示当前滑动窗口中已经包含了 T 中所有字符然后进入while 内层循环负责移动左指针 l将 左指针l 右移在不影响结果的情况收缩窗口以获得最短子字符串。 若当前滑窗长度 最小长度则刷新最小长度和左指针 l。若 左指针指向的字符 S[l] 属于T中的字符且chars[S[l]] 0即左指针再往后移的话滑动窗口就不再满足条件表示此时已是 当前 r 遍历条件下的最小窗口然后将 cnt-- 表示后续将 l 右移一步的话滑动窗口内T中的字符数量将少1。左指针 l 继续右移一步向后遍历。 最后判断滑动窗口的长度若大于S的长度表示整个S都不匹配返回空否则进行切片处理返回字符串S中左指针和右指针所截取的窗口内容。 PS为什么左指针只需要从左到右 右移一次即可不需要在每次 右指针r 遍历的情况下将左指针从左到右重新右移一遍? 答在 r 时遍历到的最小滑窗窗口比如说 [l,p] 长度是 p-l1r≥p。 在 r1 时若想要遍历到更小的窗口则滑动窗口的左指针只能继续往后移因为前面已经确定最小的滑动窗口。 #include iostream
#include vector
using namespace std;
string minWindow(string S, string T) {vectorint chars(128, 0); // ASCII表共128个字符,chars[i]代表ACII值为i的字符在T中出现的次数vectorbool flag(128, false); // flag[i]代表代表ACII值为i的字符是否出现// 先统计T中的字符情况for (int i 0; i T.size(); i) {flag[T[i]] true;chars[T[i]];}// 移动滑动窗口 不断更改统计数据int cnt 0, l 0, min_l 0, min_size S.size() 1;for (int r 0; r S.size(); r) { //接下来的外层循环通过移动窗口的右边界r来遍历字符串S。if (flag[S[r]]) { //若S[r]是T中的字符if (--chars[S[r]] 0) { //若当前窗口中还缺该字符则cntcnt;}// 若目前滑动窗口已包含T中全部字符// 则尝试将l右移 在不影响结果的情况下获得最短子字符串while (cnt T.size()) {if (r - l 1 min_size) { // 当前滑窗长度 最小长度min_l l;min_size r - l 1;}if (flag[S[l]] chars[S[l]] 0) { // 当前l缩进的窗口已经最小不再满足条件cnt--;}l; //左指针右移}}}return min_size S.size() ? : S.substr(min_l, min_size);
}int main() {string S ADOBECODEBANC, T ABC;cout minWindow(S,T);return 0;
}
