数据结构与算法之字典: Leetcode 76. 最小覆盖子串 (Typescript版)

最小覆盖子串

• 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里不同字符的个数
• 这个题目难度级别为：困难