1.题目
easy程度题
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.
Example 1:
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
Example 2:
Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
2.想法
先写出来的暴力无脑方式,将p进行sort()升序,然后创建数组temp,将p.length()个字符拷入temp中,对temp运用sort(),再strcmp()两个字符串,结果毫无疑问的运行超时!
参考别人解法后,得到思路。
用数组count存贮p字符串字符个数分布情况,
然后“滑动”S中连续的p.length()个字符,用temp数组存储S中p.length()个字符个数分布,依次往后递进,每递进一次与count比较一次。
3.AC解
class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> result;
const int N=p.length();
if(s.length()<N)
return result;
int* count=new int [26];
for(int i=0;i<26;i++)
count[i]=0;
int* temp=new int [26];
for(int i=0;i<26;i++)
temp[i]=0;
for(char a:p)
count[a-'a']++;
for(int i=0;i<N;i++)
temp[s[i]-'a']++;
if(cmp(temp,count,26))
result.push_back(0);
for(int i=N;i<s.length();i++)
{
temp[s[i-N]-'a']--;//删去前面的一个
temp[s[i]-'a']++;//加上后面的一个
if(cmp(temp,count,26))
result.push_back(i-N+1);
}
return result;
}
bool cmp(int *p1, int* p2,int N)
{
while(N--)
{
if(p1[N]!=p2[N])
return false;
}
return true;
}
};