有经验的赣州网站建设,小企业网站建设公司哪家好,建设网站都需要哪些,展览设计公司招聘最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串#xff0c;则返回空字符串 “” 。
注意#xff1a; 对于 t 中重复字符#xff0c;我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量…最小覆盖子串
给你一个字符串 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 的子串中因此没有符合条件的子字符串返回空字符串。来源力扣LeetCode 链接https://leetcode.cn/problems/minimum-window-substring
移动窗口解题思路
移动窗口通过哈希表存放模板字符频数利用左右窗口的动态移动找到包含所有模板字符的窗口子串再通过对比得到最小的子串。
首先通过size确定窗口内的字符种类数与模板字符串的字符种类数相同。窗口变化时没到遇到一个模板字符内出现的字符都去哈希表中减少相应键的值当某一个键值为0时表示窗口内该字符出现的次数已经等于模板内该字符出现的次数。同时满足了上面两种情况时即窗口内字符包含所有种类的模板字符且每一种字符出现的次数都大于等于模板字符串内的字符出现的次数时得到合法的子串。将得到的子串与上一次子串相比取长度较小的子串并再次保存。直到循环结束。
代码
/*** param {string} s* param {string} t* return {string}*/
var minWindow function(s, t) { let map new Map();//哈希表用来统计模板字符中相同字符出现的次数let nowChar ;let result;for(let i0;it.length;i){map.set(t[i],(map.get(t[i])||0)1)//统计频率}let size map.size;//记录窗口内字符对模板字符串的字符种类的抵消数为0时表示窗口内包含所有种类字符串let l 0;//定义左窗口for(let r0;rs.length;r){//对右窗口依次遍历if(map.has(s[r])) map.set(s[r],map.get(s[r])-1);//当右窗口遇到模板字符串内含有的字符时给相对应的该字符键对应的值减1if(map.get(s[r])0) size--;//当循环中遇到哈希表中值为0的键时对记录的字符种类数减1while(!size){//当循环到使字符种类数为0时即窗口中现在包含所有的模板字符串。准备移动左窗口nowChars.substring(l,r1);//因为此时窗口内字符串符合要求所有我们先截取它们并保存到临时字符串中if(map.has(s[l])){//移动左窗口前先判断左窗口是否为模板字符串的字符种类数中的一种即是否在哈希表中//如果左窗口的字符时模板字符串中的一种移动势必回导致窗口内的字符模板字符串内的那几种字符频率发生变化即相应字符减少一个map.set(s[l],map.get(s[l])1);//所有哈希表的该字符频数恢复一个if(map.get(s[l])1){//当一个字符的频数恢复到1时我们需要知道窗口内即将少一种模板字符串内的种类size;//给记录抵消数的size加1再进入下一次循环if(!result || result.lengthnowChar.length) result nowChar;//此时记录对比保存小的字符串。}}l;//如果不在则左窗口向右移动一位}}return result;
};
