最小覆盖子串

[louzhedong]

习题

出处：LeetCode 算法第76题

给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路

用一个map保存所有T中字符的个数，顺序遍历S。

解答

var minWindow = function (s, t) {
  var result = '';

  var map = {};
  t.split('').forEach(item => map[item] = (map[item] || 0) + 1);

  var count = Object.keys(map).length;

  var l = 0, r = -1;
  while (r < s.length) {
    if (count == 0) {
      if (!result || r - l + 1 < result.length) {
        result = s.slice(l, r + 1);
      }
      if (map[s[l]] !== undefined) {
        map[s[l]]++;
      }
      if (map[s[l]] > 0) {
        count++;
      }
      l++;
    } else {
      r++;
      if (map[s[r]] !== undefined) {
        map[s[r]]--;
      }
      if (map[s[r]] == 0) {
        count--;
      }
    }
  }
  return result;
};