苏州高端网站设计项目外包平台
最小覆盖子串
- https://leetcode.cn/problems/minimum-window-substring/description/
描述
- 给你一个字符串 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 的子串中，因此没有符合条件的子字符串，返回空字符串。
提示
- m == s.length
- n == t.length
- 1 <= m, n <= 105
- s 和 t 由英文字母组成
进阶
- 你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
算法实现
1 ）双指针滑动窗口遍历
function minWindow(s: string, t: string): string {let l = 0;let r = 0;// 维护一个字典，表示子串需要的字符(键)以及长度(值)let m = new Map();// 遍历模板字符串t 用字典存储for(let c of t) {// 这样遍历，可以包含模板字符串t中存在重复的字符m.set(c, m.has(c) ? m.get(c) + 1 : 1);}// 哨兵变量 mSize 用于存储字典中字符的长度let mSize = m.size;// 用于存储输出结果let res = '';while(r < s.length) {let c = s[r];// 如果字典中有该值，那么字典中就不需要了if (m.has(c)) {// 比如s中遇到了A, 在m中有A, 那么在m中A就不再需要了// 如果模板字符串t中含有多个A, 那么此处减少一个Am.set(c, m.get(c) - 1);// 字典中相关字符已经用完if(!m.get(c)) {mSize--;}}// 此处监听mSize是否全部用完while(!mSize) {let newRes = s.substring(l, r + 1);if(!res || newRes.length < res.length) {res = newRes;}// 拿到左指针let c2 = s[l];if(m.has(c2)) {m.set(c2, m.get(c2) + 1);if(m.get(c2) === 1) {mSize ++;}}l++; // 左指针移动}r++; // 右指针移动}return res;
}
- 解题思路: 先找出所有的包含T的子串,找出长度最小那个子串，返回即可
- 用双指针维护一个滑动窗口，用于枚举所有子串
- 移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度
- 循环上述过程，找出包含T的最小子串
- 时间复杂度：O(m+n) = O(n)
- m是t的长度
- n是s的长度，两个while嵌套也是O(n), 就是移动两个指针
- 空间复杂度：O(m)
- m是t里不同字符的个数
- 这个题目难度级别为：困难