最小覆盖字串

力扣第 76 题最小覆盖子串

题目描述

给你一个字符串 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) 时间内解决此问题的算法吗？

题目分析

给定字符串 s，t，从 s 中找到一个字串，使得它包含 t 中所有的字符，并且这个字串要是最小的。

解题思路

遍历 t，统计每个字符串出现的次数，存到 needMap 中
给字符串 s 设计左右指针 left 和 right，从第 0 个开始循环
当右指针小于字符串 s 的长度时，继续往右移动
设计一个变量 count，记录 t 中的字符出现的次数，设计一个windowMap,记录窗口中的字符出现的次数，当本次字符 windowMap[c] 和 needMap[c] 个数相等，说明此字符出现的次数符合要求，count++
如果 count 等于 needMap 的 size，说明本次窗口符合要求，记录本次的窗口的起始位置，然后左指针往右移动
如果移动前左边字符存在于 needMap，那么 count--，本次字符不符合要求
遍历结束，如果右指针等于 infinity，说明没有找到符合条件的字串，返回空字符串，否则返回 s 中的子串

代码实现

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function (s, t) {
  /**
   * 前提：字串要求是和原字符串一样的顺序 并且 t 字符出现的顺序不一定与字串相等，字符数量一致即可
   * 1.设置一个左右指针，作为滑动窗口边界
   * 2.t 中出现的字符串计数 滑动窗口内出现额字符串数字也计数，
   * 并设置一个 charCount，每次遇到相符的字符串+1
   * 3.遍历边界 右指针滑到最右端停止
   * 4. 当符合字串的要求与上一次对比，如果比上次短，则替换开始和结束节点
   *
   */
  const sLen = s.length;
  const tLen = t.length;
  if (tLen > sLen) return "";
  // 左右指针
  let left = 0;
  let right = 0;
  // 记录 window 中出现字符串次数
  const windowMap = new Map();
  const needMap = new Map();
  // 符合字符串计数
  let charCount = 0;
  for (let i = 0; i < tLen; i++) {
    let preCount = needMap.get(t[i]) || 0;
    needMap.set(t[i], preCount + 1);
  }
  let preLeft = left;
  let preRight = Infinity;
  // 循环停止条件 右指针探到数组最右边
  while (right < sLen) {
    // 右边指针靠右走
    // 当 charCount 和 needMap 的 size 相等，说明滑动窗口找到符合的字串
    // if (charCount === needMap.size) {
    const c = s[right];
    const count = windowMap.get(c) || 0;
    windowMap.set(c, count + 1);
    if (windowMap.get(c) === needMap.get(c)) {
      charCount++;
    }
    while (charCount === needMap.size) {
      // 比较本次窗口和上次窗口大小
      if (preRight - preLeft > right - left) {
        preLeft = left;
        preRight = right;
      }
      const ls = s[left];
      //left++ 缩小窗口
      left++;
      // 如果存在目标值
      if (needMap.has(ls)) {
        // 当数量是相同的时候才需要减1
        if (windowMap.get(ls) === needMap.get(ls)) {
          charCount--;
        }
        // 滑动串口出现计数操作
        windowMap.set(ls, windowMap.get(ls) - 1);
      }
    }
    right++;
  }
  return preRight === Infinity ? "" : s.slice(preLeft, preRight + 1);
};

最小覆盖字串 ​

题目描述 ​

题目分析 ​

解题思路 ​

代码实现 ​

最小覆盖字串

题目描述

题目分析

解题思路

代码实现