当前位置：首页 > article >正文

【练习】【滑动窗口】力扣热题100 438. 找到字符串中所有字母异位词

article 2025/2/23 20:40:23

题目

找到字符串中所有字母异位词

给定两个字符串 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” 的异位词。

来源：力扣热题100 438. 找到字符串中所有字母异位词

思路（注意事项）

数据量较大时，用数组记录滑动窗口字母出现的频率比哈希表效率高一些

纯代码1（哈希表）

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        unordered_map<char,int> p_count, s_count;

        for (int i = 0; i < p.size(); i ++) p_count[p[i]] ++;
        for (int i = 0; i < p.size() - 1; i ++) s_count[s[i]] ++;

        for (int i = p.size() - 1; i < s.size();  i ++)
        {
            s_count[s[i]] ++;
            if (p_count == s_count) ans.push_back(i - p.size() + 1); 
            s_count[s[i - p.size() + 1]] --;
            if (s_count[s[i - p.size() + 1]] == 0) s_count.erase (s[i - p.size() + 1]);
        } 

        return ans;
    }
};

题解1（加注释）

class Solution {
public:
    // 该函数用于在字符串 s 中找出所有字符串 p 的异位词的起始索引
    std::vector<int> findAnagrams(std::string s, std::string p) {
        // 用于存储所有满足条件的异位词的起始索引
        std::vector<int> ans;
        // 用于统计字符串 p 中每个字符的出现次数
        std::unordered_map<char, int> p_count;
        // 用于统计当前滑动窗口内字符串 s 中每个字符的出现次数
        std::unordered_map<char, int> s_count;

        // 遍历字符串 p，统计其中每个字符的出现次数
        for (int i = 0; i < p.size(); i++) {
            p_count[p[i]]++;
        }

        // 初始化滑动窗口，先统计字符串 s 中前 p.size() - 1 个字符的出现次数
        for (int i = 0; i < p.size() - 1; i++) {
            s_count[s[i]]++;
        }

        // 开始移动滑动窗口，从第 p.size() - 1 个位置开始，直到字符串 s 的末尾
        for (int i = p.size() - 1; i < s.size(); i++) {
            // 将当前字符 s[i] 加入到滑动窗口中，并更新其出现次数
            s_count[s[i]]++;

            // 比较当前滑动窗口内字符的出现次数 s_count 和字符串 p 中字符的出现次数 p_count
            // 如果两者相等，说明当前滑动窗口内的字符串是 p 的异位词
            if (p_count == s_count) {
                // 计算当前异位词在字符串 s 中的起始索引，并添加到结果向量 ans 中
                ans.push_back(i - p.size() + 1);
            }

            // 将滑动窗口的最左侧字符移除，并更新其出现次数
            s_count[s[i - p.size() + 1]]--;

            // 如果该字符的出现次数变为 0，从 s_count 中删除该字符，避免不必要的比较
            if (s_count[s[i - p.size() + 1]] == 0) {
                s_count.erase(s[i - p.size() + 1]);
            }
        }

        // 返回存储所有满足条件的起始索引的向量 ans
        return ans;
    }
};

纯代码2（数组）


class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans, p_count(26), s_count(26);
        if (p.size() > s.size()) return ans;        
        
        for (int i = 0; i < p.size(); i ++) p_count[p[i] - 'a'] ++;
        for (int i = 0; i < p.size() - 1; i ++) s_count[s[i] - 'a'] ++;

        for (int i = p.size() - 1; i < s.size();  i ++)
        {
            s_count[s[i] - 'a'] ++;
            if (p_count == s_count) ans.push_back(i - p.size() + 1); 
            s_count[s[i - p.size() + 1] - 'a'] --;
        } 

        return ans;
    }
};

题解2（加注释）

class Solution {
public:
    // 该函数用于在字符串 s 中找出所有字符串 p 的异位词的起始索引
    std::vector<int> findAnagrams(std::string s, std::string p) {
        // ans 用于存储找到的异位词在字符串 s 中的起始索引
        std::vector<int> ans;
        // p_count 是一个长度为 26 的数组，用于统计字符串 p 中每个小写字母的出现次数
        // 数组索引 0 - 25 分别对应字母 'a' - 'z'
        std::vector<int> p_count(26);
        // s_count 同样是长度为 26 的数组，用于统计当前滑动窗口内字符串 s 中每个小写字母的出现次数
        std::vector<int> s_count(26);

        // 如果字符串 p 的长度大于字符串 s 的长度，那么 s 中不可能存在 p 的异位词，直接返回空数组
        if (p.size() > s.size()) return ans;

        // 遍历字符串 p，统计其中每个小写字母的出现次数
        // 通过字符减去 'a' 得到对应的数组索引，比如 'a' - 'a' 得到 0，'b' - 'a' 得到 1 以此类推
        for (int i = 0; i < p.size(); i++) {
            p_count[p[i] - 'a']++;
        }

        // 初始化滑动窗口，统计字符串 s 中前 p.size() - 1 个字符里每个小写字母的出现次数
        for (int i = 0; i < p.size() - 1; i++) {
            s_count[s[i] - 'a']++;
        }

        // 开始移动滑动窗口，从第 p.size() - 1 个位置开始，直到字符串 s 的末尾
        for (int i = p.size() - 1; i < s.size(); i++) {
            // 将当前字符 s[i] 加入到滑动窗口中，并更新对应字母的出现次数
            s_count[s[i] - 'a']++;

            // 比较当前滑动窗口内每个小写字母的出现次数（s_count）和字符串 p 中每个小写字母的出现次数（p_count）
            // 如果两个数组相等，说明当前滑动窗口内的字符串是 p 的异位词
            if (p_count == s_count) {
                // 计算当前异位词在字符串 s 中的起始索引，并添加到结果数组 ans 中
                ans.push_back(i - p.size() + 1);
            }

            // 将滑动窗口的最左侧字符移除，并更新对应字母的出现次数
            s_count[s[i - p.size() + 1] - 'a']--;
        }

        // 返回存储所有满足条件的起始索引的数组 ans
        return ans;
    }
};