给定两个字符串 s
和 p
,找到 s
中所有 p
的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
思路:滑动窗口
vector<int> findAnagrams(string s, string p) {
int slen=s.size();
int plen=p.size();
if(slen<plen){
return vector<int>();
}
vector<int>ret;
vector<int>sCount(26);
vector<int>pCount(26);
for(int i=0;i<plen;i++){
pCount[p[i]-'a']++;
sCount[s[i]-'a']++;
}
if(pCount==sCount){
ret.emplace_back(0);
}
for(int i=0;i<slen-plen;i++){
sCount[s[i]-'a']--;
sCount[s[i+plen]-'a']++;
if(sCount==pCount){
ret.emplace_back(i+1);
}
}
return ret;
}