原题链接🔗：找到字符串中所有字母异位词
难度：中等⭐️⭐️
题目
给定两个字符串 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 仅包含小写字母
题解
滑动窗口法
- 题解：
理解异位词：两个字符串是异位词，意味着它们包含相同的字符，并且每个字符出现的次数也相同，但是字符的排列顺序可以不同。
滑动窗口：使用滑动窗口的方法来遍历字符串 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;
}
- 输出结果：
Start indices of anagrams of “abc” in “cbaebabacd” are:
0
6
