アルゴリズム_文字列の順列

Algorithem_PermutationInString#

与えられた 2 つの文字列 s1 と s2 があります。s2 が s1 の順列を含んでいる場合は true を、それ以外の場合は false を返します。

つまり、s1 の順列の 1 つが s2 の部分文字列である場合は true を返します。

例 1：

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

Explanation: s2はs1の1つの順列（"ba"）を含んでいます。

例 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 が 1 回、b が 1 回、c が 1 回出現します。したがって、キーが Character で値が出現回数の辞書を使用して、まず s1 を保存し、s2 と同じ長さの substring も同じタイプの辞書を生成し、2 つの辞書のキーと値が一致するかどうかを比較することで比較できます。

以下はコードです：


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