Open sl1673495 opened 4 years ago
76.最小覆盖子串
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。
示例:
输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC"
说明:
如果 S 中不存这样的子串,则返回空字符串 ""。 如果 S 中存在这样的子串,我们保证它是唯一的答案。
https://leetcode-cn.com/problems/minimum-window-substring
根据目标字符串 t生成一个目标 map,记录每个字符的目标值出现的次数。 然后就是维护一个滑动窗口,并且针对这个滑动窗口中的字符也生成一个 map 去记录字符出现次数。
t
每次循环都去对比窗口的 map 里的字符是否能覆盖目标 map 里的字符。
覆盖的意思就是,目标 map 里的每个字符在窗口 map 中出现,并且出现的次数要 >= 目标 map 中此字符出现的次数。
窗口滑动逻辑:
两种情况下停止循环,返回结果:
给定字符长度 - 目标字符的长度
/** * @param {string} s * @param {string} t * @return {string} */ let minWindow = function (s, t) { // 先制定目标 根据t字符串统计出每个字符应该出现的个数 let targetMap = makeCountMap(t) let sl = s.length let tl = t.length let left = 0 // 左边界 let right = -1 // 右边界 let countMap = {} // 当前窗口子串中 每个字符出现的次数 let min = "" // 当前计算出的最小子串 // 循环终止条件是两者有一者超出边界 while (left <= sl - tl && right <= sl) { // 和 targetMap 对比出现次数 确定是否满足条件 let isValid = true Object.keys(targetMap).forEach((key) => { let targetCount = targetMap[key] let count = countMap[key] if (!count || count < targetCount) { isValid = false } }) if (isValid) { // 如果满足 记录当前的子串 并且左边界右移 let currentValidLength = right - left + 1 if (currentValidLength < min.length || min === "") { min = s.substring(left, right + 1) } // 也要把map里对应的项去掉 countMap[s[left]]-- left++ } else { // 否则右边界右移 addCountToMap(countMap, s[right + 1]) right++ } } return min } function addCountToMap(map, str) { if (!map[str]) { map[str] = 1 } else { map[str]++ } } function makeCountMap(strs) { let map = {} for (let i = 0; i < strs.length; i++) { let letter = strs[i] addCountToMap(map, letter) } return map } console.log(minWindow("aa", "a"))
76.最小覆盖子串
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。
示例:
说明:
如果 S 中不存这样的子串,则返回空字符串 ""。 如果 S 中存在这样的子串,我们保证它是唯一的答案。
https://leetcode-cn.com/problems/minimum-window-substring
思路
根据目标字符串
t
生成一个目标 map,记录每个字符的目标值出现的次数。 然后就是维护一个滑动窗口,并且针对这个滑动窗口中的字符也生成一个 map 去记录字符出现次数。每次循环都去对比窗口的 map 里的字符是否能覆盖目标 map 里的字符。
覆盖的意思就是,目标 map 里的每个字符在窗口 map 中出现,并且出现的次数要 >= 目标 map 中此字符出现的次数。
窗口滑动逻辑:
两种情况下停止循环,返回结果:
给定字符长度 - 目标字符的长度
,此时不管匹配与否,都是最短能满足的了。