橘色网站模板,网站编程语言哪个好,链接怎么做,能先做网站再绑定域名吗题目链接#xff1a; https://leetcode.cn/problems/minimum-window-substring/ 视频题解#xff1a; https://www.bilibili.com/video/BV1sJ4m1g727/ LeetCode 76. 最小覆盖子串
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s … 题目链接 https://leetcode.cn/problems/minimum-window-substring/ 视频题解 https://www.bilibili.com/video/BV1sJ4m1g727/ LeetCode 76. 最小覆盖子串
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。
注意
对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串我们保证它是唯一的答案。
举个例子
输入s ADOBECODEBANC, t ABC
输出BANC
解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。视频题解
最小覆盖子串
思路来源
思路来源
思路解析
本题是经典的滑动窗口类型解决这类问题的关键是窗口左右边界的滑动策略。
定义hash表u_mapT保存字符串t中字符的频率hash表u_mapWindow保存滑动窗口中字符出现的次数left保存窗口的左边界right保存窗口的右边界resStart保存最小候选窗口的起点resLen保存最小候选窗口长度。
窗口滑动策略如下
u_mapT中的元素不全在u_mapWindow中right向右滑动并更新u_mapWindow[s[right]]直到u_mapT中的元素全在u_mapWindow中。u_mapT中的元素全在u_mapWindow中left向右滑并更新u_mapWindow[s[left]]--、最小候选窗口的起点resStart和最小候选窗口长度resLen直到u_mapT中的元素不全在u_mapWindow中。
根据上面的策略我们可以获得以s任意位置为左边界(枚举左边界)的所有候选窗口只需要把其中最短的一个窗口返回即可。
这里在判断u_mapT中的元素是否完全在u_mapWindow中并没有采用遍历u_mapT对其中的元素一个个去u_mapWindow中比较。而是借用了一个整型变量tInWindow在窗口滑动的过程中就对窗口中字符情况进行统计大大节省了每次判断都要去遍历hash表的时间。
C代码
class Solution {
public:string minWindow(string s, string t) {int s_len s.length();int t_len t.length();if (s_len 0 || t_len 0) {return ;}//保存t中字符出现的次数unordered_mapchar, int u_mapT;//保存window中的字符出现的次数unordered_mapchar, int u_mapWindow;//统计t中的字符for (int i 0; i t_len; i) {u_mapT[t[i]];}//t中不重复字符的个数int tCount u_mapT.size();//window完全包含t中不重复字符的数量int tInWindow 0;int resStart 0, resLen INT_MAX;int left 0, right 0;while (right s_len) {u_mapWindow[s[right]];//假设字符a在t和window中出现的次数相等就增加tInWindow的计数if (u_mapT.count(s[right]) u_mapWindow[s[right]] u_mapT[s[right]]) {tInWindow;} while (tInWindow tCount) {//窗口的大小小于已保存的最小长度更新最小长度if (right - left 1 resLen) {resStart left;resLen right - left 1; }//右移窗口左边界缩小窗口 u_mapWindow[s[left]]--;if (u_mapT.count(s[left]) u_mapT[s[left]] u_mapWindow[s[left]]) {--tInWindow;}left;}right;} if (resLen INT_MAX) return ;return s.substr(resStart, resLen);}
};java代码
class Solution {public String minWindow(String s, String t) {int s_len s.length();int t_len t.length();if (s_len 0 || t_len 0) {return ;}//保存t中字符出现的次数MapCharacter, Integer u_mapT new HashMap();//保存window中的字符出现的次数MapCharacter, Integer u_mapWindow new HashMap();//统计t中的字符for (int i 0; i t_len; i) {u_mapT.put(t.charAt(i), u_mapT.getOrDefault(t.charAt(i), 0) 1);}//t中不重复字符的个数int tCount u_mapT.size();//window完全包含t中不重复字符的数量int tInWindow 0;int resStart 0, resLen Integer.MAX_VALUE;int left 0, right 0;while (right s_len) {u_mapWindow.put(s.charAt(right), u_mapWindow.getOrDefault(s.charAt(right), 0) 1);//假设字符a在t和window中出现的次数相等就增加tInWindow的计数if (u_mapT.containsKey(s.charAt(right)) u_mapWindow.get(s.charAt(right)).equals(u_mapT.get(s.charAt(right)))) {tInWindow;}while (tInWindow tCount) {//窗口的大小小于已保存的最小长度更新最小长度if (right - left 1 resLen) {resStart left;resLen right - left 1;}//右移窗口左边界缩小窗口u_mapWindow.put(s.charAt(left), u_mapWindow.get(s.charAt(left)) - 1);if (u_mapT.containsKey(s.charAt(left)) u_mapWindow.get(s.charAt(left)) u_mapT.get(s.charAt(left))) {--tInWindow;}left;}right;}if (resLen Integer.MAX_VALUE) return ;return s.substring(resStart, resStart resLen);}
}python代码
class Solution:def minWindow(self, s: str, t: str) - str:s_len len(s)t_len len(t)if s_len 0 or t_len 0:return #保存t中字符出现的次数u_mapT defaultdict(int)#保存window中的字符出现的次数u_mapWindow defaultdict(int)#统计t中的字符for char in t:u_mapT[char] 1#t中不重复字符的个数tCount len(u_mapT)#window完全包含t中不重复字符的数量tInWindow 0resStart, resLen 0, float(inf)left, right 0, 0while right s_len:u_mapWindow[s[right]] 1#假设字符a在t和window中出现的次数相等就增加tInWindow的计数if s[right] in u_mapT and u_mapWindow[s[right]] u_mapT[s[right]]:tInWindow 1while tInWindow tCount:#窗口的大小小于已保存的最小长度更新最小长度if right - left 1 resLen:resStart leftresLen right - left 1#右移窗口左边界缩小窗口u_mapWindow[s[left]] - 1if s[left] in u_mapT and u_mapWindow[s[left]] u_mapT[s[left]]:tInWindow - 1left 1right 1if resLen float(inf):return return s[resStart:resStart resLen]复杂度分析
时间复杂度 因为使用变量tInWindow提前预先保存了window中是否包含t的字符并且只需要遍历一遍s和t所以时间复杂度为O(m n)其中m是s的长度n是t的长度。
空间复杂度 使用了两个hash表具体的复杂度和字符集的大小有关。
