Skip to main content

字符串的排列

Tips

题目类型: 滑动窗口

相关题目:

题目​

给定两个字符串 s1 和 s2, 写一个函数来判断 s2 是否包含 s1 的排列; 换句话说, 第一个字符串的排列之一是第二个字符串的子串.

提示:
  • 输入的字符串只包含小写字母
  • 两个字符串的长度都在 [1, 10000] 之间
示例
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
输入: s1= "ab" s2 = "eidboaoo"
输出: False

题解​

标准的滑动窗口问题, 写好模版即可, 该题的关键点是缩小窗口的时机是窗口区间长度大于等于 s1 的长度, 这样才有可能将 s1 包含在内, 即 right - left >= s1.length.

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var checkInclusion = function (s1, s2) {
  const needMap = new Map()

  // 将 s1 的每个元素映射到 hashmap 中
  for (const letter of s1) {
    if (needMap.has(letter)) {
      needMap.set(letter, needMap.get(letter) + 1)
    } else {
      needMap.set(letter, 1)
    }
  }

  const needLen = needMap.size
  const windowMap = new Map()

  let left = 0
  let right = 0
  let meetCount = 0

  while (right < s2.length) {
    const rightLetter = s2[right]
    right++

    if (needMap.has(rightLetter)) {
      if (windowMap.has(rightLetter)) {
        windowMap.set(rightLetter, windowMap.get(rightLetter) + 1)
      } else {
        windowMap.set(rightLetter, 1)
      }

      if (needMap.get(rightLetter) === windowMap.get(rightLetter)) {
        meetCount++
      }
    }

    // 缩小窗口的时机是窗口区间长度大于等于 s1 的长度, 这样才有可能将 s1 包含在内
    // 即 right - left >= s1.length
    while (right - left >= s1.length) {
      // 一旦 meetCount === needLen, 也就找到了子串, 此时直接返回 true 完活
      if (meetCount === needLen) {
        return true
      }

      const leftLetter = s2[left]
      left++

      if (needMap.has(leftLetter)) {
        if (needMap.get(leftLetter) === windowMap.get(leftLetter)) {
          meetCount--
        }

        windowMap.set(leftLetter, windowMap.get(leftLetter) - 1)
      }
    }
  }

  return false
}