力扣热门100题之最小覆盖子串【困难】【滑动窗口】

题目描述

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

注意：

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

示例 1：

示例 2：

示例 3:

提示：

解法1：暴力破解

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    if(t.length>s.length) return "";
    if(t==s)return s;
    let map=new Map();
    let tempMap=new Map();
    let key="";
    for(let i=0;i<t.length;i++)
    {   
        key=t.charAt(i);
        map.set(key,map.has(key)?map.get(key)+1:1);
    }
    let res="";
    console.log(map)
    for(let i=0;i<s.length;i++){
        key=s.charAt(i);
        if(map.has(key)){
            tempMap=new Map(map);
            for(let j=i;j<s.length;j++){
                key=s.charAt(j);
                if(tempMap.has(key)){
                    tempMap.set(key,tempMap.get(key)-1);
                    if(tempMap.get(key)==0){
                        tempMap.delete(key);
                        if(tempMap.size==0){
                            if(res==""||res.length>j-i){
                                res=s.substring(i,j+1);
                            }
                            break;
                        }
                    }
                }
                
            }
        }
    }
    return res;
};

执行结果：

解法2 滑动窗口

var minWindow = function(s, t) {
			if (t.length > s.length) return "";
			if (t == s) return s;
			let map = new Map();
			let tempMap = new Map();
			let key = "";
			for (let i = 0; i < t.length; i++) {
				key = t.charAt(i);
				map.set(key, map.has(key) ? map.get(key) + 1 : 1);
				tempMap.set(key, 0);
			}
			let left = -1;
			let minStr = s + ".c";
			for (let i = 0; i < s.length; i++) {
				key = s.charAt(i);
				if (map.has(key)) {
					if (left == -1) {
						left = i;
					}
					tempMap.set(key, tempMap.get(key) + 1)
					while (equals(map, tempMap)) {
						//找到一个子串
						if (minStr.length > i - left) {
							minStr = s.substring(left, i + 1);
						}
						//移出最左
						let leftKey = s.charAt(left);
						tempMap.set(leftKey, tempMap.get(leftKey) - 1);
						left++;
						leftKey = s.charAt(left);
						while (!map.has(leftKey)&&left<i) {
							left++;
							leftKey = s.charAt(left);
						}
						tempMap.set(key, tempMap.get(key) - 1)
						i--;
					}
				}
			}
			return minStr==s+".c"?"":minStr;
		};

		function equals(map, tempMap) {
			for (let key of map.keys()) {
				if (map.get(key) > tempMap.get(key)) {
					return false;
				}
			}
			return true;
		}

执行结果

滑动窗口优化

var minWindow = function(s, t) {
			if (t.length > s.length) return "";
			if (t == s) return s;
			let map = new Map();
			let tempMap = new Map();
			let key = "";
			for (let i = 0; i < t.length; i++) {
				key = t.charAt(i);
				map.set(key, map.has(key) ? map.get(key) + 1 : 1);
				tempMap.set(key, 0);
			}
			let left = -1;
			let minStr = s + ".c";
            let right=0;
            while(left<right&&right<s.length){
                key=s.charAt(right);
                if (map.has(key)) {
					if (left == -1) {
						left = right;
					}
                    tempMap.set(key, tempMap.get(key) + 1)
                    while (equals(map, tempMap)) {
						//找到一个子串
    
						if (minStr.length > right - left) {
							minStr = s.substring(left, right + 1);
						}
						//移出最左
						let leftKey = s.charAt(left);
						tempMap.set(leftKey, tempMap.get(leftKey) - 1);
                    	left++;
						leftKey = s.charAt(left);
						while (!map.has(leftKey)&&left<right) {
							left++;
							leftKey = s.charAt(left);
						}
                        continue;
					}
                }
                right++;
            }
			return minStr==s+".c"?"":minStr;
		};

		function equals(map, tempMap) {
			for (let key of map.keys()) {
				if (map.get(key) > tempMap.get(key)) {
					return false;
				}
			}
			return true;
		}

执行结果：