LeetCode 算法：找到字符串中所有字母异位词c++

原题链接🔗：找到字符串中所有字母异位词
难度：中等⭐️⭐️

题目

给定两个字符串 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 * 10⁴
s 和 p 仅包含小写字母

题解

滑动窗口法

题解：

理解异位词：两个字符串是异位词，意味着它们包含相同的字符，并且每个字符出现的次数也相同，但是字符的排列顺序可以不同。

滑动窗口：使用滑动窗口的方法来遍历字符串 s，窗口的大小与字符串 p 的长度相等。

字符计数：使用哈希表（unordered_map）来记录字符串 p 中每个字符的出现次数。

窗口内字符匹配：在滑动窗口的过程中，使用另一个哈希表来记录当前窗口内的字符及其出现次数，并与 p 中的字符计数进行比较。

更新窗口：每次向右移动窗口时，添加新的字符到窗口的哈希表中，并从窗口中移除一个字符。

判断异位词：如果在某个时刻，当前窗口内的字符计数与 p 中的字符计数相匹配，则说明找到了一个异位词，记录此时窗口的起始索引。

继续滑动：继续滑动窗口直到遍历完整个字符串 s。

返回结果：返回所有找到的异位词子串的起始索引列表。

复杂度：时间复杂度 O(n * m)，空间复杂度 O(m)。
代码过程：

初始化一个哈希表 pCount 来存储 p 中字符的出现次数。

初始化两个指针 left 和 right，分别指向当前考虑的窗口的起始和结束位置。

使用一个哈希表 windowCount 来存储当前窗口内的字符计数。

扩展窗口，直到窗口的大小等于 p 的长度。

当窗口大小等于 p 的长度时，检查当前窗口是否是 p 的异位词：

如果是，记录下 left 指针的位置，因为这是子串的起始索引。
移动 right 指针来扩展窗口，并更新 windowCount。

移动left 指针来收缩窗口，并更新 windowCount。

重复步骤 5 和 6，直到 right 指针遍历完整个字符串 s。

返回记录的所有起始索引。

c++ demo：

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

class Solution {
public:
    std::vector<int> findAnagrams(const std::string& s, const std::string& p) {
        std::vector<int> result;
        if (s.size() < p.size()) return result; // 如果s的长度小于p的长度，不可能有异位词

        // 用于存储p中字符的频率
        std::unordered_map<char, int> pFreq;
        for (char c : p) {
            pFreq[c]++;
        }

        // 用于存储当前窗口的字符频率
        std::unordered_map<char, int> windowFreq;

        int left = 0, right = 0; // 左右指针，定义当前窗口
        int validChars = 0; // 当前窗口中与p中字符匹配的字符数量

        // 窗口大小小于p时，继续扩展窗口
        while (right < s.size() && right - left < p.size()) {
            char c = s[right];
            if (pFreq.find(c) != pFreq.end()) {
                windowFreq[c]++;
            }
            right++;
        }

        // 当窗口大小等于p时，开始检查是否为异位词
        while (right - left == p.size()) {
            // 如果当前窗口是p的异位词，记录起始索引
            if (isAnagram(pFreq, windowFreq)) {
                result.push_back(left);
            }

            // 移动窗口
            char leftChar = s[left];
            if (pFreq.find(leftChar) != pFreq.end()) {
                if (windowFreq[leftChar] == pFreq[leftChar]) {
                    validChars--;
                }
                windowFreq[leftChar]--;
                if (windowFreq[leftChar] < pFreq[leftChar]) {
                    validChars++;
                }
            }

            left++;

            // 扩展窗口
            if (right < s.size()) {
                char rightChar = s[right];
                if (pFreq.find(rightChar) != pFreq.end()) {
                    windowFreq[rightChar]++;
                    if (windowFreq[rightChar] == pFreq[rightChar]) {
                        validChars--;
                    }
                }
                right++;
            }
        }

        return result;
    }

private:
    // 辅助函数，用于比较两个字符计数映射是否相等
    bool isAnagram(const std::unordered_map<char, int>& pFreq,
        const std::unordered_map<char, int>& windowFreq) {
        for (const auto& kv : pFreq) {
            if (kv.second != windowFreq.at(kv.first)) {
                return false;
            }
        }
        return true;
    }
};

int main() {
    Solution solution;
    std::string s = "cbaebabacd";
    std::string p = "abc";

    std::vector<int> anagramIndices = solution.findAnagrams(s, p);

    std::cout << "Start indices of anagrams of \"" << p << "\" in \"" << s << "\" are:" << std::endl;
    for (int index : anagramIndices) {
        std::cout << index << std::endl;
    }

    return 0;
}