Leetcode 438

题目要求

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

核心算法和原理

• 不定长滑窗策略：
• 用cnt[c] 记录子串中「还未匹配的c的数量」
• 先初始化为p中c的个数
• 然后在s中右移右指针r，每次cnt[s[r] - 'a']--
• 如果发现某个cnt[c]小于0则开始右移左指针，每次cnt[s[l] - 'a']++ ，直到cnt[c] == 0
• 当窗口长度 == p.size()时，说明匹配成功（因为保证了所有cnt都大于等于0，即不会存在过度匹配的问题）

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        #define nums(i) (i - 'a')

        vector<int> ans;
        int n = s.size(), m = p.size();
        if (n < m) {
            return ans;
        }

        int cnt[26]{};
        for (char c: p) {
            cnt[nums(c)]++;
        }

        int l = 0, r;
        for (r = 0; r < n; r++) {
            int c = s[r];
            cnt[nums(c)]--;

            // the cnt of c is too big 
            while (cnt[nums(c)] < 0) {
                // move l ->
                cnt[nums(s[l])]++;
                l++;
            }
            // if size of window == m
            // then it is an anagram of p
            if (r - l + 1 == m) {
                ans.push_back(l);
            }
        }

        return ans;
        #undef nums(i)
    }
};