438. Find All Anagrams in a String

  • 33.5%

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.

1
2
3
4
5
6
7
8
9
10
11
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".
1
2
3
4
5
6
7
8
9
10
11
12
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".

解题思路

使用数组做一个简单哈希表,另外一个数组每次进行预算,向前移动一次,增加一个元素,减去最前面的元素,每次与标准哈希表比较,确定是否加进去。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int cs[26] = {}, cp[26] = {};
vector<int> res;
for(int i=0; i<(int)p.length(); i++){
cp[p[i]-'a']++;
}
for(int i=0; i<(int)s.length(); i++){
cs[s[i]-'a']++;
if(i>=p.length())
cs[s[i-p.length()]-'a']--;
bool flag = true;
for(int j=0; j<26; j++)
flag &= cs[j] == cp[j];
if(flag==true)
res.push_back(i-p.length()+1);
}
return res;
}
};
谢谢你,可爱的朋友。