【解題筆記】Leetcode#567 — Permutation in String

Photo by Chris Ried on Unsplash

還不清楚如何運用Sliding Window方法解題，可以先參考【演算法筆記】Sliding Window 文章

Problem

題號：Leetcode 567
標題：Permutation in String
演算法：Sliding Window

Solution

class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        var s1Count = Array(repeating:0, count: 26)
        var winCount = Array(repeating:0, count: 26)

        let a = Character("a").asciiValue!

        //用陣列去記錄s1字串中a-z出現的次數
        for char in s1 {
            let index = Int(char.asciiValue! - a)
            s1Count[index] += 1
        }

        var s2Array = Array(s2)

        //擴增window範圍：遍歷s2所有元素
        for (right, char) in s2Array.enumerated() {
            
            //用陣列去記錄s2字串中a-z出現的次數
            let index = Int(char.asciiValue! - a)
            winCount[index] += 1

            //當window範圍大於s1字串長度時，將left指標向右移動縮減window
            if right >= s1.count {
                let left = right - s1.count
                let index = Int(s2Array[left].asciiValue! - a)
                //將移除字母，從陣列扣除次數
                winCount[index] -= 1
            }

            //每次window範圍改變時，檢查目前winCount是否等於s1Count
            if s1Count == winCount {
                return true
            }
        }
        return false
    }
}