567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false。

换句话说，s1 的排列之一是 s2 的 子串 。

提示：
s1 和 s2 仅包含小写字母

示例一：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

示例二：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

解题方法：双指针（滑动窗口）

class Solution {
    func getChar(_ s: String, at offset: Int) -> Character {
        return s[s.index(s.startIndex, offsetBy: offset)]    
    }
    
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        let s1Length = s1.count
        let s2Length = s2.count
        
        var s1Freq = [Character: Int]()
        var winFreq = [Character: Int]()
        var s1Count = 0
        var winCount = 0

        for i in 0..<s1Length {
            let char = getChar(s1, at: i)
            s1Freq[char, default: 0] += 1
        }
        
        for (_, value) in s1Freq {
            s1Count += 1
        }
        
        var left = 0
        var right = 0
        while right < s2Length {
            let rightChar = getChar(s2, at: right)
            if s1Freq[rightChar] != nil {
                winFreq[rightChar, default: 0] += 1
                if winFreq[rightChar] == s1Freq[rightChar] {
                    winCount += 1
                }
            }
            
            right += 1
            
            while s1Count == winCount {
                if right - left == s1Length {
                    return true
                }
                let leftChar = getChar(s2, at: left)
                if s1Freq[leftChar] != nil {
                    winFreq[leftChar, default: 0] -= 1
                    if winFreq[leftChar]! < s1Freq[leftChar]! {
                        winCount -= 1
                    }
                }
                left += 1
            }
        }
        
        return false
    }
}

解题思路

• 排列不讲究顺序，但是字符出现的 种类 和 次数 要恰好对应相等；
• 思考可以使用双指针（一前一后、交替向右边移动）的原因：少考虑很多暴力解法须要考虑的子区间，已经得到了一部分子区间的信息以后，很多子区间都不必要考虑，因此根据特定的情况右指针、左指针交替向右移动，从时间复杂度 O(N^2) 降到 O(N)；
• 由于我们只关心子区间里的元素的种数和各个字符出现的次数。因此须要统计字符串 s1 出现的字符的种数和次数，和在字符串 s2 上的两个变量所确定的滑动窗口中出现的字符种数和次数；
• 还须要设计一个变量 winCount，表示滑动窗口在 s2 上滑动的时候，出现在 s1 中的字符的种类数，规则如下：
  • 如果某一个字符出现的次数恰好等于 s1 中对应字符出现的次数，winCount += 1；
  • 在左边界向右移动的过程当中，某一个字符对应的次数减少以后，恰好小于了 s1 对应的字符出现的次数，winCount -= 1；
  • 当滑动窗口中出现的字符种类数和 s1 中出现的字符种类数相等（根据 winCount 的定义，对应次数也相等），并且 s2 上的滑动窗口的长度等于字符串 s1 的长度的时候，就找到了 s1 的一个排列。

注意：请大家特别留意 winCount 的含义：滑动窗口中的字符要满足字符出现的次数 大于等于 s1 中对应字符出现的次数的时候才加 1，winCount 不仅统计了种类，还代表了次数。使得我们可以通过 winCount 的数值去了解整个滑动窗口的信息。

复杂度分析

• 时间复杂度：O(∣s1∣+∣s2∣+∣Σ∣)； 这里 ∣s1∣ 表示字符串 s1 的长度，这里 ∣s2∣ 表示字符串 s2 的长度。Σ 表示字符集，即 s1 和 s2 中出现的所有的字符，∣Σ∣ 是字符集的大小，取决于出现字符的最小 ASCII 值和最大 ASCII 值。
  • 统计 s1 的频数数组：O(∣s1∣)；
  • 计算 s1 中出现的字符种类遍历了频数数组一次：O(∣Σ∣)；
  • 双指针遍历了 s2 一次 O(∣s2∣)。

• 空间复杂度：O(∣Σ∣)。

参考链接

• 力扣题目
• 字符串的排列解法