Leetcode 567. 字元串的排列

給你兩個字元串 s1 和 s2 ，寫一個函數來判斷 s2 是否包含 s1 的排列。如果是，傳回 true ；否則，傳回 false 。

換句話說，s1 的排列之一是 s2 的 子串 。

示例 1：

輸入：s1 = "ab" s2 = "eidbaooo"
輸出：true
解釋：s2 包含 s1 的排列之一 ("ba").      

示例 2：

輸入：s1= "ab" s2 = "eidboaoo"
輸出：false      

• 1 <= s1.length, s2.length <= 104
• s1 和 s2 僅包含小寫字母

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        
        // 排除異常的邊界情況，也限定了模式串的長度
        if(s1.size() > s2.size()) return false;
        
        // 比對采用的視窗大小為模式串大小
        int windowSize = s1.size();
        
        // 模式串的字典：可以看做一種頻率分布
        vector<int> hashmap1(26, 0);
        // 動态更新的比對視窗字典
        vector<int> hashmap2(26, 0);
        
        // 建構字典
        for(int i = 0; i < windowSize; i++) {
            hashmap1[s1[i] - 'a']++;
            hashmap2[s2[i] - 'a']++;
        }
        
        // 對于每一輪滑窗查詢，如果兩個字典相等(頻率分布一緻)，則命中
        for(int i = windowSize; i < s2.size(); i++) {
            // 兩個字典相等(頻率分布一緻)，則命中
            if(hashmap1 == hashmap2) return true;
            
            // 否則，向右滑窗：滑窗對于 hash 表的操作變為對應頻率的增減
            hashmap2[s2[i - windowSize] - 'a']--;
            hashmap2[s2[i] - 'a']++;
        }
        
        // 整個算法采用左閉右開區間，是以最後還有一個視窗沒有判斷
        return hashmap1 == hashmap2;
    }
};