Algorithem_PermutationInString

2022-04-24

Algorithem_PermutationInString

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true

Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

1 2	Input: s1 = "ab", s2 = "eidboaoo" Output: 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
    }
}