Leetcode76最小覆盖子串(滑动窗口解法)
【摘要】 Leetcode76最小覆盖子串(滑动窗口解法)给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 注意:对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保证它是唯一的答案。答题:/** * @param {string} s...
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
注意:
对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保证它是唯一的答案。
答题:
/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function (s, t) {
let l = 0;
let r = 0;
let res = "";
const m = new Map();
for (let i = 0; i < t.length; i++) {
const c = t[i];
// 放入字典表
m.set(c, m.has(c) ? m.get(c) + 1 : 1);
}
let needType = m.size;
while (r < s.length) {
const c = s[r];
if (m.has(c)) {
m.set(c, m.get(c) - 1);
if (m.get(c) === 0) needType -= 1;
}
while (needType === 0) {
const c2 = s[l];
let newRes = s.slice(l, r + 1);
if (!res || newRes.length < res.length) res = newRes;
if (m.has(c2)) {
m.set(c2, m.get(c2) + 1);
if (m.get(c2) === 1) needType += 1;
}
l++;
}
r++;
}
return res;
};
解题思路:滑动窗口的解题要点主要在于窗口什么时候向右移动,什么时候左侧缩小
就这道题而言,我们需要做的就是首先向右移动,然后找到一个包含所需字符串的位置,这时候是第一个满足要求的子串,然后窗口左侧缩小,直到不满足条件为止,然后窗口继续向右移动,直到右侧移动到头,左侧也不需要再移动为止。
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)