sliding window O(m+n) time O(1) space
跟30. Substring with Concatenation of All Words解法基本一样
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int f[26] = {0};
for (char c : p) {
++f[c - 'a'];
}
vector<int> res;
for (int m = s.length(), n = p.length(), cnt = 0, i = 0; i < m; ++i) {
if (--f[s[i] - 'a'] >= 0) {
++cnt;
}
if (i >= n && ++f[s[i - n] - 'a'] > 0) {
--cnt;
}
if (cnt == n) {
res.push_back(i - n + 1);
}
}
return res;
}
};
|
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) {
vector<int> mp(26), mc(26);
for (char c : p) {
++mp[c - 'a'];
}
vector<int> res;
int m = p.length(), n = s.length();
for (int i = 0; i < n; ++i) {
++mc[s[i] - 'a'];
if (i >= m - 1) {
if (mc == mp) {
res.push_back(i - m + 1);
}
--mc[s[i - m + 1] - 'a'];
}
}
return res;
}
};
|