本文主要是介绍LeetCode76.最小覆盖子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 题目大意
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
2. 思路分析
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
这个题的暴力方法很好想，优化的思路本质上是怎么缩短字符串的比对时间。这种情况下一般都是空间换时间。下面介绍一下算法流程。
由于目标t中会有重复的元素，所以可以设置一个计数器，数值为t的长度。为了满足s的子串中含有t的所有字母，可以用哈希表（字典）存储t中每个字母的数量。
在遍历s的时候，还是采用滑动窗口的思路左下标i，右下标j：
- 从0开始，不断地增加j。对于
s[j]， 如果当前元素在t中，则哈希表对应字母的value-1，计数器也-1 - 如果计数器=0，说明当前窗口已经包含
t的所有元素了，但是它可能不是最小的元素，开始尝试着缩小窗口，即保持j不变，i+1。每移除一个s[j]哈希表对应字母的value+1，计数器也+1。 - 在缩小窗口的过程中，如果发现计数器已经>0，说明当前窗口不完整包含
t中的所有的元素，则继续增加窗口大小，j++。
3. 代码示例
Java版本
class Solution {public String minWindow(String S, String t) {int sl = S.length();int tl = t.length();if (sl < tl) return "";Map<Character, Integer> map = new HashMap<>();String res = "";int min_len = sl+1; // 长度判断int i = 0; // 左坐标int need_count = tl;char[] s = S.toCharArray();// 统计t中的字符数for (char c : t.toCharArray()) {map.put(c, map.getOrDefault(c, 0) + 1);}for (int j = 0; j < sl; j++) {if (map.containsKey(s[j])) {int jvalue = map.get(s[j]) - 1;map.put(s[j], jvalue);if (jvalue >= 0) {need_count--;}}// 当前窗口完全包含t，进行结果保存, 窗口缩放while (need_count == 0) {// 如果发现更短的子串if ((j - i + 1) < min_len) {res = S.substring(i, j + 1);min_len = j - i + 1;}// 不断减少左下标, 缩小窗口,直到发现不包含t中的元素则need_count+1if (map.containsKey(s[i])) {int ivalue = map.get(s[i]) + 1;map.put(s[i], ivalue);if (ivalue > 0) {need_count++;}}i++;}}return res;}}
Python版本
class Solution:def minWindow(self, s: str, t: str) -> str:lens, lent = len(s), len(t)res = ""count_t = Counter(t) # 对t的每个字符计数need_count = lent # 等待匹配的数 min_len = lens+1 # 长度判断i = 0 # 左下标for j, item in enumerate(s):if item in count_t:count_t[s[j]] -= 1if count_t[s[j]] >= 0:need_count -= 1# 当前窗口完全包含t，进行结果保存, 窗口缩放while need_count == 0:# 发现更短的子串if j-i+1 < min_len:res = s[i:j+1]min_len = j-i+1# 不断减少左下标, 缩小窗口,直到发现不包含t中的元素则need_count+1if s[i] in count_t:count_t[s[i]] += 1if count_t[s[i]] > 0:need_count += 1i+=1return res
这篇关于LeetCode76.最小覆盖子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
