一线大厂高级前端编写,前端初中阶面试题,帮助初学者应聘,需要联系微信:javadudu

精读《算法题 – 最小覆盖子串》

今天我们看一道 leetcode hard 难度题目:最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 ""

注意:

对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:

输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A''B''C'

思考

最容易想到的思路是,s 从下标 0~n 形成的子串逐个判断是否满足条件,如:

  • ADOBEC..
  • DOBECO..
  • OBECOD..

因为最小覆盖子串是连续的,所以该方法可以保证遍历到所有满足条件的子串。代码如下:

function minWindow(s: string, t: string): string {
  // t 剩余匹配总长度
  let tLeftSize = t.length
  // t 每个字母对应出现次数表
  const tCharCountMap = {}

  for (const char of t) {
    if (!tCharCountMap[char]) {
      tCharCountMap[char] = 0
    }
    tCharCountMap[char]++
  }

  let globalResult = ''

  for (let i = 0; i < s.length; i++) {
    let currentResult = ''
    let currentTLeftSize = tLeftSize
    const currentTCharCountMap = { ...tCharCountMap }

    // 找到以 i 下标开头,满足条件的字符串
    for (let j = i; j < s.length; j++) {
      currentResult += s[j]
      
      // 如果这一项在 t 中存在,则减 1
      if (currentTCharCountMap[s[j]] !== undefined && currentTCharCountMap[s[j]] !== 0) {
        currentTCharCountMap[s[j]]--
        currentTLeftSize--
      }

      // 匹配完了
      if (currentTLeftSize === 0) {
        if (globalResult === '') {
          globalResult = currentResult
        } else if (currentResult.length < globalResult.length) {
          globalResult = currentResult
        }
        break
      }
    }
  }

  return globalResult
};

我们用 tCharCountMap 存储 t 中每个字符出现的次数,在遍历时每次找到出现过的字符就减去 1,直到 tLeftSize 变成 0,表示 s 完全覆盖了 t

这个方法因为执行了 n + n-1 + n-2 + … + 1 次,所以时间复杂度是 O(n²),无法 AC,因此我们要寻找更快捷的方案。

滑动窗口

追求性能的降级方案是滑动窗口或动态规划,该题目计算的是字符串,不适合用动态规划。

那滑动窗口是否合适呢?

该题要计算的是满足条件的子串,该子串肯定是连续的,滑动窗口在连续子串匹配问题上是不会遗漏结果的,所以肯定可以用这个方案。

思路也很容易想,即:如果当前字符串覆盖 t,左指针右移,否则右指针右移。就像一个窗口扫描是否满足条件,需要右指针右移判断是否满足条件,满足条件后不一定是最优的,需要左指针继续右移找寻其他答案。

这里有一个难点是如何高效判断当前窗口内字符串是否覆盖 t,有三种想法:

第一种想法是对每个字符做一个计数器,再做一个总计数器,每当匹配到一个字符,当前字符计数器与总计数器 +1,这样直接用总计数器就能判断了。但这个方法有个漏洞,即总计数器没有包含字符类型,比如连续匹配 100 个 b,总计数器都 +1,此时其实缺的是 c,那么当 c 匹配到了之后,总计数器的值并不能判定出覆盖了。

第一种方法的优化版本可能是二进制,比如用 26 个 01 表示,但可惜每个字符出现的次数会超过 1,并不是布尔类型,所以用这种方式取巧也不行。

第二种方法是笨方法,每次递归时都判断下 s 字符串当前每个字符收集的数量是否超过 t 字符串每个字符出现的数量,坏处是每次递归都至多多循环 25 次。

笔者想到的第三种方法是,还是需要一个计数器,但这个计数器 notCoverChar 是一个 Set<string> 类型,记录了每个 char 是否未 ready,所谓 ready 即该 char 在当前窗口内出现的次数 >= 该 char 在 t 字符串中出现的次数。同时还需要有 sCharMaptCharMap 来记录两个字符串每个字符出现的次数,当右指针右移时,sCharMap 对应 char 计数增加,如果该 char 出现次数超过 tchar 出现次数,就从 notCoverChar 中移除;当左指针右移时,sCharMap 对应 char 计数减少,如果该 char 出现次数低于 tchar 出现次数,该 char 重新放到 notCoverChar 中。

代码如下:

function minWindow(s: string, t: string): string {
  // s 每个字母出现次数表
  const sCharMap = {}
  // t 每个字母对应出现次数表
  const tCharMap = {}
  // 未覆盖的字符有哪些
  const notCoverChar = new Set<string>()

  // 计算各字符在 t 出现次数
  for (const char of t) {
    if (!tCharMap[char]) {
      tCharMap[char] = 0
    }
    tCharMap[char]++
    notCoverChar.add(char)
  }

  let leftIndex = 0
  let rightIndex = -1
  let result = ''
  let currentStr = ''

  // leftIndex | rightIndex 超限才会停止
  while (leftIndex < s.length && rightIndex < s.length) {
    // 未覆盖的条件:notCoverChar 长度 > 0
    if (notCoverChar.size > 0) {
      // 此时窗口没有 cover t,rightIndex 右移寻找
      rightIndex++
      const nextChar = s[rightIndex]
      currentStr += nextChar
      if (sCharMap[nextChar] === undefined) {
        sCharMap[nextChar] = 0
      }
      sCharMap[nextChar]++
      // 如果 tCharMap 有这个 nextChar, 且已收集数量超过 t 中数量,此 char ready
      if (
        tCharMap[nextChar] !== undefined &&
        sCharMap[nextChar] >= tCharMap[nextChar]
      ) {
        notCoverChar.delete(nextChar)
      }
    } else {
      // 此时窗口正好 cover t,记录最短结果
      if (result === '') {
        result = currentStr
      } else if (currentStr.length < result.length) {
        result = currentStr
      }
      // leftIndex 即将右移,将 sCharMap 中对应 char 数量减 1
      const previousChar = s[leftIndex]
      sCharMap[previousChar]--
      // 如果 previousChar 在 sCharMap 数量少于 tCharMap 数量,则不能 cover
      if (sCharMap[previousChar] < tCharMap[previousChar]) {
        notCoverChar.add(previousChar)
      }
      // leftIndex 右移
      leftIndex++
      currentStr = currentStr.slice(1, currentStr.length)
    }
  }
  
  return result
};

其中还用了一些小缓存,比如 currentStr 记录当前窗口内字符串,这样当可以覆盖 t 时,随时可以拿到当前字符串,而不需要根据左右指针重新遍历。

总结

该题首先要排除动态规划,并根据连续子串特性第一时间想到滑动窗口可以覆盖到所有可能性。

滑动窗口方案想到后,需要想到如何高性能判断当前窗口内字符串可以覆盖 tnotCoverChar 就是一种不错的思路。

讨论地址是:精读《算法 – 最小覆盖子串》· Issue #496 · dt-fe/weekly

如果你想参与讨论,请 点击这里,每周都有新的主题,周末或周一发布。前端精读 – 帮你筛选靠谱的内容。

版权声明:自由转载-非商用-非衍生-保持署名(创意共享 3.0 许可证

原文链接:https://juejin.cn/post/7266703104112918580 作者:黄子毅

(0)
上一篇 2023年8月14日 上午10:16
下一篇 2023年8月14日 上午10:26

相关推荐

发表评论

登录后才能评论