题目描述
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
样例
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
C++ 代码
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int>res;
unordered_map<char,int>mp;
unordered_map<char,int>target;
for(auto c:p)target[c]++;
string str1=s.substr(0,p.size());
for(auto c:str1)mp[c]++;
int i=0,j=p.size()-1;
while(j<s.size()){
if(mp==target)res.push_back(i);
mp[s[i]]--;
if(mp[s[i]]==0)mp.erase(s[i]);
mp[s[j+1]]++;
i++,j++;
}
return res;
}
};
看了下时间,应该是刚好卡过去了,应该算比较暴力的解法,用了两个map,一个是存p中字符出现次数的map,一个是用来存s的滑动窗口的map,一开始一直卡在滑动窗口的map,有一半样例过不去,因为我等价的条件是两个map要相等,后来仔细一想,那些map中字符为0的记录应该被删除,否则这些为值0的记录,会卡出我们想要和p的map相等的要求。
应对上面的bug,我们只需要在窗口左移时,判断一下移出的元素在map中的值是否已经为0了,这些都是冗杂的信息,需要删除。
```