刷题 | Leetcode 567. Permutation in String | Sliding Window

蛮力算法不难想出，穷举即可，但明显会超时。需要考虑如何避免多余计算。

可以用一个移动窗口，也就是用下标 i 和 j 框出一个子字符串，能包含所有 s1 中的字符，这个字符串通常是包含了其他字母的，如果没有，那么它的长度是和 s1 字符串一样的。

移动窗口方法，可以说在字符串匹配和查找问题中屡试不爽。

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        // idea:
        // sliding window
        // Move i, j as two pointers through s2,
        // find a sub-string of s2 which contain
        // all the characters in s1.
        // The hard part is how to deal with the
        // moving one step right-ward.  
        int m[26] = {};
        int count = 0;
        for(char c : s1) {
            m[c-‘a‘]++;
        }
        for(int i = 0, j = 0; j < s2.size() && count < s1.size(); j++) {
            if(m[s2[j]-‘a‘] > 0) {
                m[s2[j]-‘a‘]--;
                count++;
            } else {
                while(s2[i] != s2[j]) {
                    m[s2[i]-‘a‘]++;
                    i++;
                    count--;
                }
                i++;
            }
        }
        return count == s1.size();
    }
};

刷题 | Leetcode 567. Permutation in String | Sliding Window

原文：https://www.cnblogs.com/casperwin/p/12914397.html