AlgoPress | AlgoPress

0076-最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

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

示例 2：

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

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

1 <= s.length, t.length <= 10^5
s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

思路：暴力法【未完成】

暴力法，以 t 的长度作为窗口，依次遍历 s ，判断是否包含目标字符串的字符，如果没有，就增加窗口长度。注意：t的字符必须都要在s中，也就是说同样的字符，匹配一次之后，要从s中删掉比如：s = "bbaa" , t = "aba"，结果是 baa 而不是 bba

参考代码

csharp

public class Solution {

	private bool Contains(string s, int start, int window, string t){
		string source = s.Substring(start, window);
		foreach(char c in t){
			if(!source.Contains(c)){
				return false;
			}
		}
		return true;
	}

    public string MinWindow(string s, string t) {
    	if(s.Length < t.Length){
    		return false;
    	}
    	int window = t.Length;
    	while(window <= s.Length){
    		for(int i=0; i <= s.Length - window; i++){
	    		if(Contains(s,i,window,t)){
	    			return s.Substring(i,window);
	    		}
	    	}
	    	window++;
    	}
    	return "";
    }
}

思路2：滑动窗口

O(n) 就是遍历常数遍，使用哈希表储存窗口中的数字，遍历目标
分为两个字典存放字符的个数，如果满足条件之后，就开始收缩窗口

csharp

public class Solution {

	private bool Contains(Dictionary<char,int> dictSource, Dictionary<char,int> dictTarget){
		foreach(char key in dictTarget.Keys){
			if(!dictSource.ContainsKey(key) || dictSource[key] < dictTarget[key]){
				return false;
			}
		}
		return true;
	}

	private void AddDict(Dictionary<char,int> dict, char key){
		if(!dict.ContainsKey(key)){
			dict.Add(key,1);
		}
		else{
			dict[key]++;
		}
	}


	public string MinWindow(string s, string t){
		int window = int.MaxValue;
		int left = 0;
        int len = t.Length;

        if(s.Length < t.Length){ //边界条件
            return "";
        }

        Dictionary<char,int> dictSource = new Dictionary<char,int>();
        Dictionary<char,int> dictTarget = new Dictionary<char,int>();

		//将数据加到字典中
		for(int i=0; i<len; i++){
            //Console.WriteLine("add source 1 {0}",s[i]);
			AddDict(dictSource, s[i]);
			AddDict(dictTarget, t[i]);
		}
		//检测是否已经满足
		if(Contains(dictSource,dictTarget)){
			return s.Substring(0,len);
		}
		//延展滑动窗口
        string ans = "";
		for(int j=left+len; j<s.Length; j++){
            //Console.WriteLine("add source 2 {0}",s[j]);
            AddDict(dictSource,s[j]);	
			
			while(Contains(dictSource,dictTarget)){
                if(window > j - left + 1){
                    window = j - left + 1;
                    //当满足条件的时候就记录结果值，必须是当前最小的时候记录，不要直接设置为 min
                    ans = s.Substring(left,window);
                }                
				//收缩滑动窗口
                //Console.WriteLine("remove source {0}",s[left]);
				dictSource[s[left]]--;
                left++;
			}
		}
		return ans;
	}
}

复杂度分析：
时间复杂度：for循环只有一遍 O(n) 哈希表判断 O(m) 总体复杂度 O(m*n)
空间复杂度：两个hash表最多储存n个key，复杂度为 O(n)

优化滑动窗口，第一部分只需要加入 source, 第二部分直接处理滑动窗口

思路2：优化时间复杂度

遍历目标窗口，加入字符。
开始收缩窗口：当该字符符合条件的时候 dictSource[s[j]] <= dictTarget[s[j]] 总的 count + 1
当 dictSource[s[j]] > dictTarget[s[j]] 的时候，压缩窗口
当 count 正好等于 t.Length 的时候，说明找到结果，注意根据 ans 的情况更新值 (ans = "" 或者 ans 的长度大于目前的长度)
https://leetcode.cn/problems/minimum-window-substring/solution/leetcode-76-zui-xiao-fu-gai-zi-chuan-cja-lmqz/

csharp

public class Solution{
	private void AddDict(Dictionary<char,int> dict, char key){
		if(!dict.ContainsKey(key)){
            dict.Add(key,1);
		}
        else{
            dict[key]++;
        }
	}

	public string MinWindow(string s, string t){
		Dictionary<char,int> dictSource = new Dictionary<char,int>();
		Dictionary<char,int> dictTarget = new Dictionary<char,int>();	
		int count = 0;
		string ans = "";
		for(int i=0; i<t.Length; i++){
			AddDict(dictTarget,t[i]);
		}
		//滑动窗口
		int j=0; //j表示滑动窗口的左边,i表示滑动窗口的右边
		for(int i=0; i<s.Length; i++){
			AddDict(dictSource,s[i]);
			if(dictTarget.ContainsKey(s[i]) && dictSource[s[i]] <= dictTarget[s[i]]){
				//刚刚添加进去之后，还小于等于目标字符，说明有效，累计count
				count++;
			}
			//收缩窗口，如果目标窗口不包含左边字符,或者左边所在的字符已经大于目标字符
			while(j<i && (!dictTarget.ContainsKey(s[j]) || dictSource[s[j]] > dictTarget[s[j]])){
				dictSource[s[j]]--;
				j++;
			}

			if(count == t.Length){ //如果刚好相等，说明就是答案，注意以前的ans必须大于当前答案才更新
				if(ans == "" || ans.Length > i-j+1){
					ans = s.Substring(j,i-j+1);	
				}
			}
		}
		return ans;
	}
}

复杂度分析：遍历一次 dict O(n) 哈希表记录了次数

复习：20220510

两个哈希表统计比较字符串， left -> i 双指针滑动窗口。

csharp

public class Solution {
    private void AddDict(Dictionary<char,int> dict, char key){
        if(dict.ContainsKey(key)){
            dict[key]++;
        }
        else{
            dict.Add(key,1);
        }
    }

    private bool ContainsDict(Dictionary<char,int> source, Dictionary<char,int> target){
        if(source.Keys.Count < target.Keys.Count){
            return false;
        }
        foreach(char key in target.Keys){
            if(!source.ContainsKey(key) || source[key] < target[key]){
                return false;
            }
        }
        return true;
    }
    
    public string MinWindow(string s, string t) {    
        //滑动窗口
        Dictionary<char,int> source = new Dictionary<char,int>();
        Dictionary<char,int> target = new Dictionary<char,int>();

        //添加目标值
        for(int i=0; i<t.Length; i++){
            AddDict(target, t[i]);
        }

        string result = "";
        int left = 0;

        //循环添加source
        for(int j=0; j<s.Length; j++){
            AddDict(source,s[j]);
            while(ContainsDict(source,target)){ //查看source是否包含target
                //记录答案
                if(result == "" || result.Length > j-left+1){
                    result = s.Substring(left,j-left+1);
                }
                //收缩滑动窗口
                source[s[left]]--; //删除source个数
                left++; //收缩窗口
            }
        }

        return result;

    }
}

0076-最小覆盖子串 #

思路：暴力法【未完成】 #

参考代码 #

思路2：滑动窗口 #

思路2：优化时间复杂度 #

复习：20220510 #

0076-最小覆盖子串

思路：暴力法【未完成】

参考代码

思路2：滑动窗口

思路2：优化时间复杂度

复习：20220510