【LeetCode】438.找到字符串中所有的字母异位词

题目

题目链接：LeetCode-438题

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

题目要求

1. 异位词 的子串
2. 起始索引

什么是“异位词”？

异位词是指两个字符串的字符组成完全相同，但字符的顺序可以不同。例如，“abc” 和 “bca” 是异位词，而 “abc” 和 “abd” 不是。

如何快速判断两个字符串是否是“异位词”？

我们可以通过统计两个字符串中每个字符的个数来判断它们是否是异位词。如果两个字符串的字符统计结果完全相同，则它们是异位词。
利用哈希表来实现。

解法 滑动窗口 + 哈希表 （统计个数）

核心思路

1. 滑动窗口：在字符串 s 上维护一个固定大小的窗口，窗口的大小等于字符串 p 的长度。

2. 哈希表统计：使用哈希表统计窗口内字符的个数，并与 p 的字符统计结果进行比较。

3. 优化：通过变量 count 统计窗口中“有效字符”的个数，避免每次比较整个哈希表。

优化：
利用变量count来统计窗口中“有效字符”的个数

• 进窗口的字符，这个字符所对应的数如果<=对应p串对应字符的个数，则为有效字符，count++
• 出窗口的字符，如果字符对应的数在出去之前>对应p串对应的字符的个数，则为无效字符，若为有效字符，count–;

具体步骤

1. 初始化：
   • 统计字符串 p 的字符个数，存入哈希表 hashp。
   • 初始化滑动窗口的左边界 left = 0，右边界 right = 0。
   • 初始化变量 count，用于统计窗口中“有效字符”的个数。
2. 滑动窗口：
   • 右边界 right 向右移动，将字符 s[right] 加入窗口，并更新哈希表 hashs。
   • 如果当前字符 s[right] 的个数不超过 p 中对应字符的个数，则 count++（表示这是一个有效字符）。
   • 如果窗口大小超过 p 的长度，则左边界 left 向右移动，将字符 s[left] 移出窗口，并更新哈希表 hashs。
   • 如果移出的字符 s[left] 的个数不超过 p 中对应字符的个数，则 count–（表示移出了一个有效字符）。
3. 更新结果：
   • 如果 count 等于 p 的长度，说明当前窗口是一个异位词子串，记录起始索引 left。

代码

class Solution {
public:
    unordered_map<char,int> hashp;
    unordered_map<char,int> hashs;
    vector<int> ret;
    vector<int> findAnagrams(string s, string p) {
        //统计p
        for(auto ch : p)
        {
            hashp[ch] ++;
        }

        //滑动窗口
        int left = 0,right = 0;
        
        int count = 0;
        int m = p.size();
        for(right;right < s.size();right++)
        {
            char in = s[right];

            //进入窗口
            hashs[in] ++;  
            //判断是否是有效字符，维护count
            if(hashs[in]<=hashp[in]) count++; 

            if(right - left + 1 > m) 
            {
                //出窗口
                char out = s[left];
                left++;
                
                //判断是否是有效字符，维护count
                if(hashs[out]<=hashp[out]) count--;
                hashs[out]--;
            } 

            //更新结果
            if(count == m) ret.push_back(left);
        }

        return ret;
    }
};