76.最小覆盖子串

链接：76.最小覆盖子串
难度：Hard
标签：哈希表、字符串、滑动窗口
简介：给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

题解 1 - typescript

• 编辑时间：2021-11-07
• 执行用时：92ms
• 内存消耗：41MB
• 编程语言：typescript
• 解法介绍：滑动窗口。

function minWindow(s: string, t: string): string {
  let cnt = 0;
  const map: Record<string, number> = {};
  for (const ch of t) {
    map[ch] = (map[ch] ?? 0) + 1;
    if (map[ch] === 1) cnt++;
  }
  let l = 0;
  let r = 0;
  let ansLen = s.length + 1;
  let ans = '';
  while (r <= s.length) {
    if (cnt) {
      const ch = s[r];
      if (map[ch] !== undefined) {
        map[ch]--;
        if (map[ch] === 0) cnt--;
      }
      r++;
    } else {
      const ch = s[l];
      if (map[ch] !== undefined) {
        map[ch]++;
        if (map[ch] === 1) cnt++;
      }
      l++;
    }
    if (cnt === 0 && ansLen > r - l) {
      ans = s.substring(l, r);
      ansLen = ans.length;
    }
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-11-07
• 执行用时：92ms
• 内存消耗：41MB
• 编程语言：typescript
• 解法介绍：滑动窗口。

function minWindow(s: string, t: string): string {
  let cnt = 0;
  const map: Record<string, number> = {};
  for (const ch of t) {
    map[ch] = (map[ch] ?? 0) + 1;
    if (map[ch] === 1) cnt++;
  }
  let l = 0;
  let r = 0;
  let ansLen = s.length + 1;
  let ans = '';
  while (r <= s.length) {
    if (cnt) {
      const ch = s[r];
      if (map[ch] !== undefined) {
        map[ch]--;
        if (map[ch] === 0) cnt--;
      }
      r++;
    } else {
      const ch = s[l];
      if (map[ch] !== undefined) {
        map[ch]++;
        if (map[ch] === 1) cnt++;
      }
      l++;
    }
    if (cnt === 0 && ansLen > r - l) {
      ans = s.substring(l, r);
      ansLen = ans.length;
    }
  }
  return ans;
}

题解 3 - typescript

• 编辑时间：2020-05-23
• 执行用时：1400ms
• 内存消耗：43.8MB
• 编程语言：typescript
• 解法介绍：定义 i,j 指向 0，不满足条件时 j++，满足时 i++。

type CharCount = { [c: string]: number };
var minWindow = function (s: string, t: string): string {
  // 储存值
  const map: CharCount = {};
  for (const c of t) map[c] = map[c] ? map[c] + 1 : 1;
  function valid(now: CharCount) {
    for (const [k, v] of Object.entries(map)) if (!now[k] || now[k] < v) return false;
    return true;
  }
  console.log(map);
  const slen = s.length;
  const nowMap: CharCount = {};
  let i = 0,
    j = 0;
  let resi = 0,
    resj = Number.MAX_VALUE;
  let isV = false;
  while (j <= slen) {
    if ((isV = valid(nowMap))) {
      if (j - i < resj - resi) {
        resj = j;
        resi = i;
      }
    }
    if (isV) {
      const prevC = s[i++];
      if (nowMap[prevC] === 1) {
        delete nowMap[prevC];
      } else {
        nowMap[prevC]--;
      }
    } else {
      const nextC = s[j++];
      nowMap[nextC] = nowMap[nextC] ? nowMap[nextC] + 1 : 1;
    }
  }
  console.log(resi, resj);
  return resj === Number.MAX_VALUE ? '' : s.substring(resi, resj);
};