给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。
数据范围：
，保证s和t字符串中仅包含大小写英文字母
要求：进阶：空间复杂度 )
， 时间复杂度
例如：
找出的最短子串为.
注意：
如果 s 中没有包含 t 中所有字符的子串，返回空字符串 “”；
满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。
[编程题]最小覆盖子串
//主要思路是通过两次遍历找到所有可能的窗口（即从S中从start到end包含一个T），通过以下几个步骤实现：
//为了减少时间复杂度，用map记录T中所有字符出现的次数，使用count在S中寻找时计数，一旦找到一个T中的字符
//就count++，同时map中当前字符的次数减1，当count等于T的长度时，即找到了一个包含T的字符串，然后
//通过比较每个找到的字符串的长度，选择最短字符串，即为题中所求
class Solution {
public:
string minWindow(string S, string T) {
int len = T.size();
int count = 0;
int lenS = S.size();
int start=0,end=lenS;
for(int i=0;i<lenS;i++)
{
map<char,int> mp;
for(int i=0;i<len;i++)
mp[T[i]] += 1;
if(mp[S[i]]>0)
{
count = 0;
for(int j=i;j<lenS;j++)
{
if(mp[S[j]]>0)
{
count++;
mp[S[j]]--;
}
if(count==len)
{
if(j-i<end-start)
{
start = i;
end = j;
}
break;
}
}
}
}
if(start>=0 && end<lenS)
return S.substr(start,end-start+1);
return "";
}
};
发表于 2019-01-14 16:07:51
回复(2)
class Solution {
public:
string minWindow(string s, string t) {
int len = t.length();
int size = s.length();
if(size < len){
return "";
}
int record[256] = {0};
int freq[256] = {0};
for(int i = 0; i < len; ++i){
++record[t[i]];
}
int i = 0;
int j = -1;
int sum = 0;
int min_len = size;
int cur = -1;
while(i < size){
if(sum < len && j+1 < size){
++freq[s[++j]];
if(record[s[j]] && freq[s[j]] <= record[s[j]]){
++sum;
}
} if(sum >= len){
if(min_len >= j-i+1){
cur = i;
min_len = j-i+1;
}
--freq[s[i]];
if(record[s[i]] && record[s[i]] - freq[s[i]] >= 1){
--sum;
}
++i;
}
if(j == size-1 && sum < len)
break;
}
if(cur != -1){
return string(s, cur, min_len);
}else{
return "";
}
}
};
发表于 2018-04-03 00:14:05
回复(0)
//暴力求吧....感觉没啥好方法
class Solution {
public:
string minWindow(string S, string T) {
int MIN=0x7FFFFFFF;
string res="";
for(int i=0;i<S.size();i++)
{ int Cur=0;
string temp=T;
for(int j=i;j<S.size();j++)
{
for(int k=0;k<temp.size();k++)
{
if(S[j]==temp[k])
{
temp[k]='*';
Cur++;
break;
}
}
if(Cur==T.size())
{
if(j-i+1<MIN)
{
MIN=j-i+1;
res=S.substr(i,j-i+1);
}
break;
}
}
}
return res;
}
};
编辑于 2018-03-24 13:58:40
回复(0)
T有可能重复，所以需要对T中每个字符都要判断是否满足次数
class Solution(object):
def minWindow(self, s, t):
res_begin = -1
res_len = 2147483647
m = {}
m_needed = {}
for i in range(len(t)):
m[t[i]] = 0
if t[i] not in m_needed:
m_needed[t[i]] = 1
else:
m_needed[t[i]] += 1
count = 0
begin = 0
end = 0
while True:
if count < len(m_needed):
if end == len(s):
break
if s[end] in m:
m[s[end]] += 1
if m[s[end]] == m_needed[s[end]]:
count += 1
end += 1
else:
if res_len > end - begin:
res_begin = begin
res_len = end - begin
if s[begin] in m:
m[s[begin]] -= 1
if m[s[begin]] == m_needed[s[begin]] - 1:
count -= 1
begin += 1
if res_begin == -1:
return ""
else:
return s[res_begin:res_begin + res_len]
发表于 2017-10-09 13:02:12
回复(0)
class Solution {
public:
string minWindow(string S, string T) {
// 思路是在S中选一个T中的元素作为起点，来计算最短窗口
if(S == ""|| T == "")
return "";
int tlen = T.size();
int slen = S.size();
if(tlen > slen)
return "";
multiset<char> Tset; // 存T中的元素
for(int i = 0; i < tlen; i++)
Tset.insert(T[i]);
int min = 10000; // 最短窗口长度
int bindex = 10000; // 窗口的起点
for(int i = 0; i <= slen-tlen; i++)
{
if(Tset.find(S[i]) == Tset.end()) // 找一个起点
continue;
int begindex = i;
multiset<char> Ts = Tset;
int j = begindex;
for( ;!Ts.empty() && j < slen;j++)
{
auto iter = Ts.find(S[j]);
if(iter != Ts.end())
Ts.erase(iter);
// 直接用Ts.erase(S[j])会删掉所有值为S[j]的节点
}
if(Ts.empty())
{
int temp = j-begindex;
if(min > temp) // 更新最短长度
{
min = temp;
bindex = begindex;
}
}
}
if(bindex == 10000)
return "";
return S.substr(bindex,min);
}
};
编辑于 2017-08-18 14:45:06
回复(0)
import java.util.*;
public class Solution {
public String minWindow(String S, String T) {
String res = "";
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
int left = 0;
int minL = Integer.MAX_VALUE;
int count = 0;
for(int i=0; i<T.length(); i++) {
if(map.containsKey(T.charAt(i)))
map.put(T.charAt(i), map.get(T.charAt(i))+1);
else
map.put(T.charAt(i), 1);
}
for(int i=0; i<S.length(); i++) {
if(map.containsKey(S.charAt(i))) {
map.put(S.charAt(i), map.get(S.charAt(i))-1);
if(map.get(S.charAt(i)) >= 0) {
count++;
}
while(count == T.length()) {
if(map.containsKey(S.charAt(left))) {
if(i - left + 1 < minL) {
minL = i - left + 1;
res = S.substring(left, i+1);
}
map.put(S.charAt(left), map.get(S.charAt(left))+1);
if(map.get(S.charAt(left)) > 0)
count--;
}
left++;
}
}
}
return res;
}
}
编辑于 2017-06-23 12:34:10
回复(0)
这道题的思路是：
1) begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。
记录窗口长度d
2) 然后begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被
包含在窗口，
3) 继续后移end，直到T中的所有字符被包含在窗口，重新记录最小的窗口d。
4) 如此循环知道end到S中的最后一个字符。
时间复杂度为O(n)
public class Solution {
public String minWindow(String S, String T) {
int[] map = new int[128];
//init map, 记录T中每个元素出现的次数
for(int i = 0; i < T.length(); i++) {
map[T.charAt(i)]++;
}
// begin end两个指针指向窗口的首位，d记录窗口的长度， counter记录T中还有几个字符没被窗口包含
int begin = 0, end = 0, d = Integer.MAX_VALUE, counter = T.length(), head = 0;
// end指针一直向后遍历
while(end < S.length()) {
// map[] > 0 说明该字符在T中出现，counter-- 表示对应的字符被包含在了窗口，counter--, 如果s中的字符没有在T中出现，则map[]中对应的字符-1后变为负值
if(map[S.charAt(end++)]-- > 0) {
counter--;
}
// 当counter==0时，说明窗口已经包含了T中的所有字符
while (counter == 0) {
if(end - begin < d) {
d = end - (head = begin);
}
if(map[S.charAt(begin++)]++ == 0) { // begin开始后移，继续向后寻找。如果begin后移后指向的字符在map中==0，表示是在T中出现的，如果没有出现，map[]中的值会是负值。
counter++; // 在T中的某个字符从窗口中移除，所以counter++。
}
}
}
return d==Integer.MAX_VALUE ? "" :S.substring(head, head+d);
}
}
编辑于 2017-09-13 02:04:13
回复(20)
滑动窗口
在jerry之前的算法题解中，也是有过滑动窗口解法的题目。
滑动窗口，是一种框架思维：- 用
l,r表示滑动窗口的左边界和右边界，通过改变l,r来扩展和收缩滑动窗口
- 用
- 在这题目中可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串
t的所有元素，记录下这个滑动窗口的大小slze = r-l+1，这些长度中的最小值就是要求的结果。 - 主要分以下几个步骤：
- 从0开始，不断增加
r使滑动窗口增大，直到窗口包含了t的所有元素 - 从0开始，不断增加
l使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的大小，并保存最小值 mln - 让
l再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤1开始执行，寻找新的满足条件的滑动窗口，如此反复，直到r超出了字符串S范围 - 判断滑动窗口是否
包含了t中的所有元素，这是将考虑的最关键的一部分！！！
- 这里使用一个字典来记录
t中的字符以及个数，还有所需个数 - 用
need[128]来记录t中字符，字符将以ASCII形式存储 - 用
needCount表示当前遍历下，满足t还需要的元素个数 need[97]=2表示t中需要2个字符a，needCount=3表示覆盖t还需要3个字符- 每当遍历到
t中的字符，其对应的need[]应该-1 - 当
needCount==0时，则当前窗口覆盖了t中所有元素
- 其次关键是如何判断当前遍历的字符是不是
多余的字符？要是多余，就可以移除。
- 在这里，我对上面的字典
need[]多加一步操作 - 无论当前遍历字符在不在
t中，都要在need中-1 - 要是
多余字符，其对应的need[]一定是<0 - 这样的目的：利用
need[]的正负来区分字符是否多余的还是有用的
- 最后一点，无论
左边界还是右边界，在边界移动时候，要注意维护对应的参数。
class Solution {
public String minWindow(String s, String t) {
// l(left): 左边界
// r(right): 右边界
int l = 0, r = 0;
// size=r-l+1: 滑动窗口的大小，默认值Integer.MAX_VALUE方便值交换
int size = Integer.MAX_VALUE;
// needCount: 当前遍历下，满足t还需要的元素个数，默认值、最大值是t.length，为0时表示滑动窗口内容覆盖了t中所有元素
int needCount = t.length();
// start: 记录有效滑动窗口的起始位置(左边界)，方便后续查找对应的字串
int start = 0;
// 字典need: 记录滑动窗口中需要t中各个元素的数量
// ASCII方式存储 [A-Z]：65-90 [a-z]：97-122
// need[97]=2 表示t中需要2个a
// t中对应字符的need[]必须>=0
// 若need[]<0表示是个多余的字符
int[] need = new int[128];
// 根据t的内容，向字典need添加元素
for (int i = 0; i < t.length(); i++)
need[t.charAt(i)]++;
// 循环条件，右边界不能溢出
while (r < s.length()) {
// 获取当前遍历的元素字符
char c = s.charAt(r);
// 若当前遍历字符是t中的内容，needCount需要-1
if (need[c] > 0)
needCount--;
// 无论c在不在t中，都要在need中-1
// 目的：利用正负来区分字符是否多余的还是有用的
need[c]--;
// needCount==0表示当前窗口满足t中所有元素
if (needCount == 0) {
// 判断左边界是否可以收缩
// 如果l对应字符的need[]<0，表示是个多余的字符
while (l < r && need[s.charAt(l)] < 0) {
// 在need[]中维护更新这个字符
need[s.charAt(l)]++;
// 左边界向右移，移除这个多余字符
l++;
}
// 判断是否更新有效滑动窗口的大小
if (r - l + 1 < size) {
// 更新
size = r - l + 1;
// 记录有效滑动窗口的起始位置(左边界)，方便查找对应的字串
start = l;
}
// 左边界对应的字符计数需要+1
need[s.charAt(l)]++;
// 重新维护左边界
l++;
// 重新维护当前的needCount
needCount++;
}
// 右边界向右移，寻找下一满足条件的有效滑动窗口
r++;
}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}
} 时间复杂度：
。左右指针各自扫一遍字符串
s，时间复杂度是空间复杂度：
发表于 2021-08-03 16:49:09
回复(0)
class Solution {
public:
string minWindow(string S, string T) {
string result;
map<char,int>t,s;
for(auto c:T)
t[c]++;
int count=0,l=0;
for(int r=0;r<S.length();r++)
{
if(t[S[r]] != 0)
{
s[S[r]]++;
if(s[S[r]] <= t[S[r]])
count++;
while(count == T.length())
{
if(result.empty() || result.length()>r-l+1)
result = S.substr(l,r-l+1);
if(t[S[l]])
{
s[S[l]]--;
if(s[S[l]] < t[S[l]])
count--;
}
l++;
}
}
}
return result;
}
};
发表于 2017-09-05 01:58:33
回复(1)
class Solution {
public:
//维持一个窗口滑动，左边是left，右边是right，然后判断是否包含T
string minWindow(string S, string T)
{
string result;
if(!S.size() || !T.size())
{
return result;
}
map<char, int>Tmap; //存储T字符串里字符，便于与S匹配
int left = 0; //左边窗口,起始为0
int count = 0; //计数器，对窗口内T串字符数量进行计数,起始为0
//装载T串
int minlen = S.size() + 1; //最小窗口，便于比较最后取最小的,初始化取最大
for(int i = 0; i < T.size(); ++i)
{
Tmap[T[i]]++;
}
//移动右边窗口
for(int right = 0; right < S.size(); ++right)
{
if(Tmap.find(S[right]) != Tmap.end()) //当窗口内部有T中的字符
{
if(Tmap[S[right]] > 0)
{
count++; //计数器+1
}
Tmap[S[right]]--; //去掉包含的，剩下都是没包含的
while(count == T.size())//当窗口内有T的所有字符，就要开始移动左窗口啦
{
if(Tmap.find(S[left]) != Tmap.end())
{
//好了，这就是一个包含字符串的窗口范围：left ~ right,
//判断是否比当前窗口还小，是就取串
if(minlen > right - left + 1)
{
//更新窗口大小
minlen = right -left + 1;
result = S.substr(left, right - left + 1);
}
//舍弃窗口左边字符串，继续移动窗口
Tmap[S[left]]++;
if(Tmap[S[left]] > 0) //如果左边连续相同，则count不递减，窗口需要继续向右移动
{
count--;
}
}
left++; //移动左窗口
}
}
}
return result;
}
};
编辑于 2017-07-30 21:07:56
回复(7)
题目要求O(n)时间复杂度完成,我们只能使用滑动窗口来完成.由于题意的子串是需要包含字符串T的.所以我需要一个哈希表ori来记录字符串T的使用记录.题意为包含关系,我们不需要在意顺序,如果存在该字符则说明这个子串有效,更新长度
class Solution {
public:
string minWindow(string S, string T) {
//滑动窗口
unordered_map<char, int> ori,cur;
for(auto& x:T){
ori[x]++;
}
string res;
int count=0;
//i代表右窗口,j代表左边窗口
for(int i=0,j=0;i<S.size();i++){
cur[S[i]]++;
if(cur[S[i]]<=ori[S[i]]) count++;//存在该字符个数加1
//说明左窗口的字符在右边的位置可以替代,我们需要缩减窗口
while(cur[S[j]]>ori[S[j]]) cur[S[j++]]--;//左窗口移动并减少字符个数
//重复寻找最小的子串
if(count==T.size()){
if(res.empty()||i-j+1<res.size()){
res=S.substr(j,i-j+1);
}
}
}
return res;
}
};
发表于 2021-09-03 20:20:07
回复(0)
使用滑动窗口与对照数组，搞了好久😓
import java.util.*;
public class Solution {
/**
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
public String minWindow (String S, String T) {
// write code here
int[] target = new int[128];
for (char c : T.toCharArray()) {
target[c]++;
}
// 最小标距离默认取不到 miniSize.length + 1
int miniSize = S.length() + 1;
int[] resMap = new int[128];
// 已包含字符数量，起始索引
int containNum = 0, resIndex = -1;
// 使用滑动窗口遍历
int l = 0, r = -1;
char[] source = S.toCharArray();
while (r+1 < source.length) {
// 右移后，包含字符数+1 <= 目标字符数，则containNum++，其他情况视为重复或非T中字符
r++;
if (++resMap[source[r]] <= target[source[r]]) {
containNum++;
}
while (containNum == T.length()) {
if (r - l + 1 < miniSize) {
miniSize = r - l + 1;
resIndex = l;
}
// 当前字符数-1 < 目标字符数，则containNum--，非T中字符--后数量为0（相等）
if (--resMap[source[l]] < target[source[l]]) {
containNum--;
}
// l指针往右移
l++;
}
}
return miniSize == S.length() + 1 ? "" : S.substring(resIndex, resIndex+miniSize);
}
}
发表于 2021-03-26 13:36:39
回复(0)
import java.util.HashMap;
import java.util.Map;
public class Solution {
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length())
return "";
// HashMap的key为t中各个字符，value为对应字符个数
Map<Character, Integer> map = new HashMap<Character, Integer>();
for (char c : t.toCharArray()) {
if (!map.containsKey(c))
map.put(c, 0);
map.put(c, map.get(c) + 1);
}
// minLeft为最小窗口左下标，minLen为最小长度，count用来计数
int minLeft = 0, minLen = s.length() + 1, count = 0;
int left = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (map.containsKey(c)) {
// 如果map.get(c)说明t中还有字符没有包含，计数器+1
if (map.get(c) > 0){
count++;
}
map.put(c, map.get(c) - 1);
}
// 如果left到i中包含t中所有字符
while (count == t.length()) {
if (i - left + 1 < minLen) {
minLeft = left;
minLen = i - left + 1;
}
c = s.charAt(left);
if (map.containsKey(c)) {
map.put(c, map.get(c) + 1);
if (map.get(c) > 0)
count--;
}
left++;
}
}
if (minLen > s.length())
return "";
return s.substring(minLeft, minLeft + minLen);
}
}
发表于 2017-07-25 20:06:09
回复(1)
贴个Java的，参照了某位同志的思路
public class Solution {
// 从头开始检查S，如果是T中的元素，计算如果以该元素作为窗口的第一个元素
public String minWindow(String S, String T) {
if(S == null || S.length() <= 0 || T == null || T.length() <= 0)
return "";
int[] sCount = new int[256];
int[] tCount = new int[256];
for(int i = 0; i < T.length(); i++){
tCount[(int)T.charAt(i)]++;
}
int begin = 0, e_begin = 0;
int end = S.length(), e_end = S.length();
for(int i = 0; i < S.length(); i++){
// 计算以S.charAt(i)开头的最小窗口
// S.charAt(i)不是T中字符，肯定不会是开头
if(tCount[S.charAt(i)] == 0)
continue;
sCount[S.charAt(i)]++;
end = i;
boolean isFind = true;
for(int j = 0; j < 256; j++){
if(sCount[j] < tCount[j]){
isFind = false;
break;
}
}
// 找到了T中所有字符
if(isFind){
// 找到S中包含T中字符的开头
while(begin < S.length()){
int ch = S.charAt(begin);
if(tCount[ch] == 0){
begin++;
continue;
}
// 如果ch出现次数超了，那么开头指针往后
if(sCount[ch] - 1 >= tCount[ch]){
sCount[ch]--;
begin++;
}
else {
break;
}
}
// 更新最小窗口的长度
if(e_end - e_begin > end - begin){
e_end = end;
e_begin = begin;
}
}
}
if(e_end - e_begin >= S.length())
return "";
else
return S.substring(e_begin, e_end + 1);
}
}
发表于 2017-05-09 15:22:08
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
public String minWindow (String S, String T) {
// 存放目标字符串的字符数量
int[] need = new int[128];
for (int i = 0; i < T.length(); i++) need[T.charAt(i)]++;
// 目标字符串中的字符个数
int count = T.length();
// 左右指针,用于维护滑动窗口
int left = 0, right = 0;
// 记录窗口的起点与长度,用于截取字符串;长度初始化为一个不可能的最大值
int start = 0, len = S.length() + 1;
while (right < S.length()) {
// 滑动窗口右侧
char c = S.charAt(right++);
// 仅当前字符的需要数量大于0时,需要的目标字符数量减一
if (need[c] > 0) {
count--;
}
// 所有字符都进行自减操作,不需要的字符会被减到负数,需要的字符先减到0,再减到负数
need[c]--;
// 当count为0时,说明当前窗口中的字符可以覆盖目标字符串T
if (count == 0) {
// 当need中,窗口左侧的字符为负数时,说明该字符是多余的(不论是否是T中包含的字符),滑动窗口左侧,直至最左侧的字符非多余,此时窗口为右侧固定情况下的最小覆盖子串
while (need[S.charAt(left)] < 0) {
need[S.charAt(left++)]++;
}
// 判断长度,并记录起点和长度
if (right - left < len) {
len = right - left;
start = left;
}
// 将窗口左侧字符滑出,need中该字符需要的数量自增(为1)
need[S.charAt(left++)]++;
// 需要的目标字符数量也自增(为1)
count++;
}
}
// 若长度仍为不可能的最大值,说明没有覆盖子串,否则通过start和len进行截取
return len == S.length() + 1 ? "" : S.substring(start, start + len);
}
}
发表于 2023-08-09 18:11:44
回复(0)
题目：给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。
运用两个指针i和j，j负责遍历S从前往后查找包含T的子串，i负责从前往后缩短符合条件的子串，
最终结果i,j就可定位出最小字串，因为字符串截取是包含i，不包含下标j的，因此为S.substring(i-1, j);
import java.util.*;
public class Solution {
/**
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
public String minWindow (String S, String T) {
// write code here
String minstr = "";
int[] hash = new int[128];
//初始化
for(int i=0; i<T.length(); i++) {
hash[T.charAt(i)] -= 1;
}
int i = 0;
int j = 0;
while(j < S.length()) {
//j指针优先向右移动，并填充hash数组
hash[S.charAt(j)] += 1;
j++;
//如果匹配到T，则将i指针向右滑动，以查找最小覆盖子串
while(check(hash) && i<j) {
hash[S.charAt(i)] -= 1;
i++;
}
}
return S.substring(i-1, j);
}
public boolean check(int[] hash) {
for(int i=0; i<hash.length; i++) {
if(hash[i] < 0) {
return false;
}
}
return true;
}
}
发表于 2023-03-09 11:15:33
回复(2)
class Solution {
public:
/**
*
* @param S string字符串
* @param T string字符串
* @return string字符串
*/
string minWindow(string S, string T) {
// 时间复杂度O(N)，空间复杂度O(N)
unordered_map<char, int> tm, sm;
for (char &c : T) tm[c]++;
int left = 0, right = 0, start = -1, end = S.size();
while (right <= S.size()) {
if (check(tm, sm)) {
if (sm.count(S[left])) --sm[S[left]];
if (right - left < end - start) {
start = left;
end = right;
}
++left;
} else {
if (tm.count(S[right])) ++sm[S[right]];
++right;
}
}
return start == -1 ? "" : S.substr(start, end - start);
}
bool check(unordered_map<char, int> &tm, unordered_map<char, int> &sm) {
for (auto &ele : tm)
if (ele.second > sm[ele.first]) return false;
return true;
}
};
发表于 2022-10-25 11:05:55
回复(0)
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param S string字符串
# @param T string字符串
# @return string字符串
#
class Solution:
def minWindow(self , S: str, T: str) -> str:
m, M = -1, len(S)
left, right = 0, 0
sdict, tdict = {}, {}
for i in T:
if i in tdict.keys():
tdict[i] = tdict[i] + 1
else:
tdict[i] = 1
while right < len(S):
if S[right] in tdict.keys():
if S[right] in sdict.keys():
sdict[S[right]] = sdict[S[right]] + 1
else:
sdict[S[right]] = 1
else:
right = right + 1
continue
right = right + 1
flag = False
for i in tdict.keys():
if i in sdict.keys():
if tdict[i] > sdict[i]:
flag = True
else:
flag = True
if flag:
continue
while left < right:
if M-m > right - left:
m, M = left, right
tmp = S[left]
left = left + 1
if tmp in sdict.keys():
if sdict[tmp] > 1:
sdict[tmp] = sdict[tmp] - 1
if sdict[tmp] < tdict[tmp]:
break
else:
sdict.pop(tmp)
break
if m == -1:
return ''
ret = S[m:M]
return ret
发表于 2022-10-05 17:27:06
回复(0)
public String minWindow (String S, String T) {
// 统计目标字符个数（由于大小写都存在，懒得进行判断转换，直接存对应Ascii码，'z'最大）
int[] tCharCount = new int['z'+1];
for (char c : T.toCharArray()) {
tCharCount[c] ++;
}
// 左右指针滑动窗口
int hitTimes = 0;
int minLen = Integer.MAX_VALUE;
String result = "";
for (int left = 0, right = 0; right < S.length(); right++) {
tCharCount[S.charAt(right)]--;
// 命中目标字符
if (tCharCount[S.charAt(right)] > -1) {
hitTimes ++;
}
// 全部字符都命中
if (hitTimes == T.length()) {
// 移动左指针，直致有效字符
while (tCharCount[S.charAt(left)] != 0) {
tCharCount[S.charAt(left++)] ++;
}
// 记录最小值，以及对应字符
if (right-left+1 < minLen) {
result = S.substring(left, right+1);
minLen = right - left + 1;
}
// 恢复最左有效数据，命中次数-1
tCharCount[S.charAt(left++)] ++;
hitTimes --;
}
}
return result;
}
发表于 2022-09-22 17:10:06
回复(0)
哈希表 + 双指针的滑动窗口，找到包含T的所有字符，缩小窗口找到最小子串
时间复杂度：O(len(T)*len(S)+len(T)) 空间复杂度：O(len(T))
class Solution:
def check(self, mp):
for key, value in mp.items():
if value < 0:
return False
return True
def minWindow(self , S: str, T: str) -> str:
mp = {}
low = 0
high = 0
left = -1
right = -1
len_ = len(S) + 1
for i in T:
if i in mp:
mp[i] -= 1
else:
mp[i] = -1
for j in range(len(S)):
if S[high] in mp:
mp[S[high]] += 1
while self.check(mp):
if len_ > high - low + 1:
len_ = high - low + 1
left = low
right = high
if S[low] in mp:
mp[S[low]] -= 1
low += 1
high += 1
if left == -1:
return ''
return S[left:right+1]
发表于 2022-05-27 10:33:33
回复(0)
问题信息
难度：
142条回答
1316收藏
28256浏览
通过挑战的用户
-
2023-03-09 23:23:26
-
2023-03-03 20:16:20 -
2023-03-03 19:55:13
-
2023-01-28 12:19:46
-
2022-11-26 13:01:09
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
