本文最后更新于 2025-03-30T12:48:34+08:00
题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| 给你一个字符串 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 <= 105 s 和 t 由英文字母组成
进阶:你能设计一个在 o(n) 时间内解决此问题的算法吗?
|
题目思路
- 1、本题依旧使用滑动窗口解法,题目意思主要为,只要 t 中的对应字母的个数,与在 s 中截取 p 长度的那一部分的字母个数相同,求其中的最小区间即可!
- 2、与昨日题目一样,本题使用两个哈希表代替两个数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
| class Solution { public: string minWindow(string s, string t) { int n = s.size(), m = t.size(); unordered_map<char, int> wins, wint; for(auto ch: t) { wint[ch]++; } string res; int count = 0; for(int i = 0, j = 0; i < n; i++) { wins[s[i]] ++ ; if(wins[s[i]] <= wint[s[i]]) count++ ; while(wins[s[j]] > wint[s[j]]) wins[s[j++]]--; if(count == m) { if(res.empty() || i - j + 1 < res.size()) { res = s.substr(j, i - j + 1); } } } return res; } };
|
复杂度
Day 46 76. 最小覆盖子串
https://chaggle.github.io/2021/10/25/Leetcode/91-day/day-46/