Algorithem_PermutationInString

Algorithem_PermutationInString#

給定兩個字符串 s1 和 s2，如果 s2 包含 s1 的一個排列，則返回 true，否則返回 false。

換句話說，如果 s1 的任意一個排列是 s2 的子字符串，則返回 true。

示例 1:

輸入: s1 = "ab", s2 = "eidbaooo"
輸出: true

解釋: s2 包含 s1 的一個排列 ("ba")。

示例 2:

輸入: s1 = "ab", s2 = "eidboaoo"
輸出: false

解法#

首先理解 Permutation 的意思，題目需要的是 s2 包含 s1 中字符串的任意一種排列，就返回 true，否則返回 false。即比如 s1 = 'abc'，那麼 s1 的排列有 'abc'、'aca'、'bac'、'bca'、'cba'、'cab' 6 種，當字符個數越多排列的種類也越多，所以想要通過枚舉 s1 的排列，然後判斷 s2 中是否包含這些排列的方法，太麻煩。

那麼要怎麼解呢？假如 s2 包含 s1 的排列，那麼肯定是 s2 中 s1 長度的 subString 和 s1 的某種排列一樣，所以可以通過 SlidingWindow 算法

Window 的長度是 s1 的長度，從 0 開始，每次取 window 長度的 substring
如何比較 s2 的 substring 和 s1 的某種排列是否相等呢？不論 s1 的排列是什麼樣，字符出現的次數是固定的，比如 s1=abc，其中一定是 a 出現一次、b 出現一次、c 出現一次。所以用字典存儲，key 是 Character，value 是出現的次數，先把 s1 的存起來，然後把 s2 的同樣長度的 substring 也生成一個同樣類型的字典，然後比較兩個字典的 key 和 value 是否一致，從而就能比較

代碼如下：


class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        if s1.length > s2.length || s2.length == 0 {
            return false
        }
        
        if s1.length == 0 {
            return true
        }
        
        let s1CharList = Array(s1)
        let s2CharList = Array(s2)
        
        let s1Count = s1CharList.count
        let s2Count = s2CharList.count
        
        let map1: [Character: Int] = generateMap(s1CharList)
                
        for i in 0..<s2Count-s1Count+1 {
            let item = s2CharList[i]
            if map1.keys.contains(item) {
                let map2: [Character: Int] = generateMap(Array(s2CharList[i..<i+s1Count]))
                let findEqual = map1 == map2
                if findEqual {
                    return true
                }
            }
        }
        return false        
    }
 
    func generateMap(_ list: [Character]) -> [Character: Int] {
        var map1: [Character: Int] = [:]
        for t in list {
            if let tcount = map1[t] {
                map1[t] = tcount + 1
            }
            else {
                map1[t] = 1
            }
        }
        return map1
    }
}