Find All Anagrams in a String – LeetCode 438
Problem
Description
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.
Answer
Original
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> pv(26,0), sv(26,0), res;
if(s.size() < p.size())
return res;
for(int i = 0; i < p.size(); ++i)
{
++pv[p[i]-'a'];
++sv[s[i]-'a'];
}
if(pv == sv)
res.push_back(0);
for(int i = p.size(); i < s.size(); ++i)
{
++sv[s[i]-'a'];
--sv[s[i-p.size()]-'a'];
if(pv == sv)
res.push_back(i-p.size()+1);
}
return res;
}
};
|
思路
简单的建立一张表来滑动对比。依旧没有漂亮的解决比对的问题。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$34$ ms，排名$23.15\%$
Better
思路
这个也是滑动窗口，但是比对的过程设计的更加仔细，开销会小一些。时间复杂度$O(n)$，空间复杂度$O(n)$。
耗时$34$ ms，排名$23.15\%$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
vector<int> findAnagrams(string s, string p) {
if (s.empty()) return {};
vector<int> res, m(256, 0);
int left = 0, right = 0, cnt = p.size(), n = s.size();
for (char c : p) ++m[c];
while (right < n) {
if (m[s[right++]]-- >= 1) --cnt;
if (cnt == 0) res.push_back(left);
if (right - left == p.size() && m[s[left++]]++ >= 0) ++cnt;
}
return res;
}
};
|