今是昨非

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:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Solution#

First, understand the meaning of permutation. The problem requires that s2 contains any permutation of s1, and return true if it does, otherwise return false. In other words, if one of s1's permutations is a substring of s2, return true.

Example: s1 = 'abc', s1 has 6 permutations: 'abc', 'aca', 'bac', 'bca', 'cba', 'cab'. The more characters in s1, the more permutations there are. Enumerating all permutations of s1 and checking if s2 contains any of them is too cumbersome.

So how do we solve it? If s2 contains a permutation of s1, then a substring of s2 with the same length as s1 must be the same as one of the permutations of s1. Therefore, we can use the Sliding Window algorithm:

• The window length is the length of s1, starting from 0, and each time we take a substring of the window length.
• How do we compare the substring of s2 with one of the permutations of s1? Regardless of the permutation of s1, the number of occurrences of each character is fixed. For example, if s1 = 'abc', then a must appear once, b must appear once, and c must appear once. We can store this information in a dictionary, where the key is the character and the value is the number of occurrences. First, store s1 in a dictionary, and then generate a dictionary of the same type for a substring of s2 with the same length. Finally, compare the keys and values of the two dictionaries to determine if they are equal.

The code is as follows:

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
    }
}