今是昨非

title: Algorithm_PermutationInString
tags:
- Technology
- Algorithm
date: 2022-04-24 11:03#

Algorithm_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 a 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 checking if s2 contains any permutation of s1. If it does, return true; otherwise, return false. In other words, if one of s1's permutations is a substring of s2, return true.

Example: s1 = 'abc'. The permutations of s1 are 'abc', 'aca', 'bac', 'bca', 'cba', 'cab'. The number of permutations increases with the number of characters in s1. Enumerating all permutations of s1 and checking if s2 contains any of them would be too cumbersome.

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

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

Here is the code:

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