438.Find All Anagrams in a String
438.Find ALL Anagrams in a String
难度:Easy
给定一个字符串 s 和一个非空字符串 p,找到 s 中所有是 p 的字母异位词的子串,返回这些子串的起始索引。 字符串只包含小写英文字母,并且字符串 s 和 p 的长度都不超过 20100。
说明: 字母异位词指字母相同,但排列不同的字符串。 不考虑答案输出的顺序。
1
示例 1:
2
3
输入:
4
s: "cbaebabacd" p: "abc"
5
6
输出:
7
[0, 6]
8
9
解释:
10
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
11
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
12
示例 2:
13
14
输入:
15
s: "abab" p: "ab"
16
17
输出:
18
[0, 1, 2]
19
20
解释:
21
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
22
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
23
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
Copied!
方法:
  1. 1.
    最原始的比较法: Hash table按序比较,时间复杂度O(nm),提交超时。
1
class Solution {
2
public:
3
vector<int> findAnagrams(string s, string p) {
4
vector<int> res;
5
if(s==p) return res;
6
if(s.length()<p.length()) return res;
7
int len=p.size();
8
unordered_map<char,int>b1;
9
for(auto i:p)
10
b1[i]++;
11
for(int i=0;i<s.length()-len+1;i++)
12
{
13
unordered_map<char,int>a1;
14
int flag=0;
15
for(int j=i;j<i+len;j++)
16
{
17
a1[s[j]]++;
18
}
19
for(int j=i;j<i+len;j++)
20
{
21
if(a1[s[j]]!=b1[s[j]])
22
{
23
flag=1;
24
break;
25
}
26
}
27
if(!flag)
28
res.push_back(i);
29
}
30
31
return res;
32
}
33
34
};
Copied!
  1. 1.
    优化: Hash table+ slide window. 时间复杂度O(n)
1
lass Solution {
2
public:
3
vector<int> findAnagrams(string s, string p) {
4
vector<int> res;
5
vector<int>sv(26,0);
6
vector<int>pv(26,0);
7
int len=p.length();
8
for(auto c: p)
9
++pv[c-'a'];
10
for(int i=0;i<s.length();i++)
11
{
12
if(i>=len) --sv[s[i-len]-'a'];
13
++sv[s[i]-'a'];
14
if(sv == pv) res.push_back(i-len+1);
15
}
16
return res;
17
}
18
19
};
Copied!
Copy link