# LeetCode438. Find All Anagrams in a String（滑动窗口）

## LeetCode438. Find All Anagrams in a String（滑动窗口）

• Easy
• Accepted：102,812
• Submissions：285,887

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

### Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

### Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

### 链接

https://leetcode.com/problems/find-all-anagrams-in-a-string/

### 题解

• 暴力，时间复杂度$O((n-m)*m)$，n-m找到所有“可能的p”，m进行匹配看是否为p的anagrams
• 匹配的话我们可以使用哈希表，用一个数组来统计p中所有字母出现的数量，cnt[p[i]]++，如果某个字母匹配上的话可以cnt[s[i]]--，统计是否完全匹配完成即可。
• 滑动指针，时间复杂度$O(n)$，对s遍历一次，在遍历的过程中动态的与p进行匹配。初始化l和r均指向0位置，cnt数组统计p中所有字母的数量，len为p的长度，对于当前字母s[r++]如果在p中，则cnt中当前字母数量减1，len-1，当len为0时表示成功完成一次匹配，当r-l等于p的长度时完成第一次寻找，整体右移，如果当前字母s[l++]在p中时，len+1，相当于“对cnt数组复原”接着判断。（cnt值为>=0为p中字符）
• s:cbaebabacdp:abc，$\overline{cba}ebabacd \rightarrow c\overline{bae}babacd \rightarrow cb\overline{aeb}abacd...$

### 代码

• Runtime: 32 ms, faster than 53.09% of C++ online submissions for Find All Anagrams in a String.
• Memory Usage: 7 MB, less than 0.89% of C++ online submissions for Find All Anagrams in a String.
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int cnt[256] = {0};
int n = s.length(), m = p.length();
int l = 0, r = 0, len = m; // 滑动窗口为s[l r)
vector <int> ans;
for (int i = 0; i < m; ++i) // “哈希”存储
cnt[p[i]]++;
while (r < n)
{
if (cnt[s[r++]]-- >= 1) // 该字母在p中
--len;
if (len == 0) // 符合要求
ans.push_back(l);
if (r - l == m && cnt[s[l++]]++ >= 0) // 整体右移
++len;
}
return ans;
}
};
• 一种看上去更好的写法
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector <int> scnt(26, 0);
vector <int> pcnt(26, 0);
vector <int> ans;
int n = s.length(), m = p.length();
int l = 0, r = 0;
for (int i = 0; i < m; ++i)
++pcnt[p[i] - 'a'];
for (int i = 0; i < n; ++i)
{
if (i >= l) // 整体右移
--scnt[s[i - m] - 'a'];
++scnt[s[i] - 'a'];
if (scnt == pcnt) // 相等时完成匹配
ans.push_back(i - m + 1);
}
return ans;
}
};

To be continued.
2019年2月7日 星期四