《剑指 Offer》专项突破版 - 面试题 15 : 字符串中的所有变位词（C++ 实现）

题目链接：LCR 015. 找到字符串中所有字母异位词 - 力扣（LeetCode）

题目：

输入字符串 s1 和 s2，如何找出字符串 s2 的所有变位词在字符串 s1 中的起始下标？假设两个字符串中只包含英文小写字母。例如，字符串 s1 为 "cbadabacg"，字符串 s2 为 "abc"，字符串 s2 的两个变位词 "cba" 和 "bac" 是字符串 s1 中的子字符串，输出它们在字符串 s1 中的起始下标 0 和 5。

分析：

这个题目是面试题 14 "字符串中的变位词" 的变种。

《剑指 Offer》专项突破版 - 面试题 14 : 字符串中的变位词（C++ 实现）-CSDN博客

代码实现：

class Solution {
public:
 ? ?bool areAllZero(const vector<int> counts)
 ?  {
 ? ? ? ?for (int count : counts)
 ? ? ?  {
 ? ? ? ? ? ?if (count != 0)
 ? ? ? ? ? ? ? ?return false;
 ? ? ?  }
 ? ? ? ?return true;
 ?  }
?
 ? ?vector<int> findAnagrams(string s, string p) {
 ? ? ? ?vector<int> indices;
 ? ? ? ?int m = s.size(), n = p.size();
 ? ? ? ?if (m < n)
 ? ? ? ? ? ?return indices;
?
 ? ? ? ?vector<int> counts(26, 0);
 ? ? ? ?for (int i = 0; i < n; ++i)
 ? ? ?  {
 ? ? ? ? ? ?++counts[p[i] - 'a'];
 ? ? ? ? ? ?--counts[s[i] - 'a'];
 ? ? ?  }
?
 ? ? ? ?if (areAllZero(counts))
 ? ? ? ? ? ?indices.push_back(0);
?
 ? ? ? ?for (int i = n; i < m; ++i)
 ? ? ?  {
 ? ? ? ? ? ?++counts[s[i - n] - 'a'];
 ? ? ? ? ? ?--counts[s[i] - 'a'];
 ? ? ? ? ? ?if (areAllZero(counts))
 ? ? ? ? ? ? ? ?indices.push_back(i - n + 1);
 ? ? ?  }
 ? ? ? ?return indices;
 ?  }
};