Problem: 438. 找到字符串中所有字母异位词
解析
滑动窗口
维护一个长度为p.size()的窗口，每次移动窗口，判断窗口内的字符是否和p中的字符一致。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> res;
if (s.size() < p.size()) {
return res;
}
vector<int> sVector(26);
vector<int> pVector(26);
int index;
for (index = 0; index < p.size(); ++index) {
sVector[s[index] - 'a']++;
pVector[p[index] - 'a']++;
}
if (sVector == pVector) {
res.emplace_back(index - p.size());
}
for (; index < s.size(); ++index) {
sVector[s[index - p.size()] - 'a']--;
sVector[s[index] - 'a']++;
if (sVector == pVector) {
res.emplace_back(index - p.size() + 1);
}
}
return res;
}
};
|
