LeetCode-找到字符串中所有字母异位词-题解[滑动窗口

「这是我参与11月更文挑战的第11天，活动详情查看：2021最后一次更文挑战」

题目要求

题目描述

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

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例

示例 1

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
复制代码

示例 2

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
复制代码

提示

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

解题思路

题目要求很简单，类似查找字符串中所有的子串，只不过本题改了要求，不仅仅要求只是子串，要求是异位词才可以。因此，本题的一大难点就在于如何判断两个字符串是否是异位词。
根据异位词的定义，我们可以得知，只要两个字符串的字母个数相同，则可以说他们是异位词。由于跟字母出现的顺序无关，因此，我们可以将要比较的两个字符串进行排序，之后判断他们是否相等即可。
上诉是第一个思路，但是由于需要对每个子串进行比对，会耗费大量时间导致超时，因此我们考虑另一种思路。
我们可以维护两个数组，每个数组里面分别存储要比较的两个字符串的26字符的出现次数，若两个数组相等，则可以说他们是异位词。且由于每个子串是相连的，我们可以实时更新数组且不用耗费大量时间，因此该方案可行。

代码

class Solution {
public:
    int len_s, len_p;
    vector<int> findAnagrams(string s, string p) {
        len_s = s.size();
        len_p = p.size();
        vector<int> target(26, 0);
        vector<int> window(26, 0);
        vector<int> res;
        if(len_p>len_s) return res;

        for(int i=0; i<len_p; i++) target[p[i]-'a'] += 1;
        for(int i=0; i<len_p; i++){
            // if(target[s[i]-'a']-window[s[i]-'a'] == 1){
            //     false_cnt -= 1;
            // }else if(target[s[i]-'a']-window[s[i]-'a'] == 0){
            //     false_cnt += 1;
            // }
            window[s[i]-'a'] += 1;
        }
        if(window == target) res.push_back(0);

        for(int i=1; i<len_s-len_p+1; i++){
            // if(target[s[i-1]-'a']-window[s[i-1]-'a'] == -1){
            //     false_cnt -= 1;
            // }else if(target[s[i-1]-'a']-window[s[i-1]-'a'] == 0){
            //     false_cnt += 1;
            // }
            // if(target[s[i+len_p-1]-'a']-window[s[i+len_p-1]-'a'] == 1){
            //     false_cnt -= 1;
            // }else if(target[s[i+len_p-1]-'a']-window[s[i+len_p-1]-'a'] == 0){
            //     false_cnt += 1;
            // }
            window[s[i-1]-'a'] -=1;
            window[s[i+len_p-1]-'a'] += 1;
            if(window == target) res.push_back(i);
        }
        return res;
    }
};
复制代码