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 仅包含小写字母

题解

滑动窗口法

1. 题解：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. 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;
}

• 输出结果：

Start indices of anagrams of “abc” in “cbaebabacd” are:
0
6