[438] Find All Anagrams in a String

微妙 囧

這樣算是sliding windows 嗎- -+

想盡辦法把return value的output塞進while了～但還是感覺怪怪的XD

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

bool compareHash(int* s, int* t) {

for (int i=0; i<26; i++)

if (s[i]!= t[i])

return false;

return true;

}

int* findAnagrams(char* s, char* p, int* returnSize) {

int s_len = strlen(s);

int p_len = strlen(p);

*returnSize = 0;

if (p_len > s_len)

return NULL;

int *p_hash = calloc(26 , sizeof(int));

int *s_hash = calloc(26 , sizeof(int));

for (int i=0; i<p_len; i++)

{

p_hash[p[i]-'a']++;

s_hash[s[i]-'a']++;

}

int *ret = calloc( s_len-p_len+1, sizeof(int)); // alloc max first.

int l = 0;

int r = p_len;

#if 1

while (r<=s_len)

{

if (compareHash(s_hash,p_hash))

ret[(*returnSize)++] = l;

if (r==s_len)

break;

s_hash[s[r++]-'a']++;

s_hash[s[l++]-'a']--;

}

#else

if (compareHash(s_hash,p_hash))

ret[(*returnSize)++] = l;

while (r<s_len)

{

s_hash[s[r++]-'a']++;

s_hash[s[l++]-'a']--;

if (compareHash(s_hash,p_hash))

ret[(*returnSize)++] = l;

}

#endif

return ret;

}

寫一個真正的sliding window?

嗯很好～看了別人的說明還是看不懂，改成C版本之後才勉強看懂，

我還是洗洗睡吧Orz 

自己寫了一次, while (r < p_len)的地方要小心～不是拿 for i=0 to len 來做～

那樣只會跑len 次，但window的 l & r 在那邊伸縮來去實際上迴圈會跑的次數比長度還多！

以上. 

/**

* Note: The returned array must be malloced, assume caller calls free().

*/

int* findAnagrams(char* s, char* p, int* returnSize) {

int p_len = strlen (p);

int s_len = strlen (s);

int *hash = calloc (26, sizeof(26));

for (int i=0; i<p_len;i++)

hash[p[i]-'a']++;

int l=0;

int r=0;

*returnSize=0;

int *ret = calloc (s_len, sizeof(int));

while (r<s_len)

{

if (hash[s[r]-'a']>0)

{

hash[s[r++]-'a']--;

if (r-l== p_len)

ret[(*returnSize)++]=l;

}

else if (l==r)

{

l++;

r++;

}

else

{

hash[s[l++]-'a']++;

}

}

return ret;

}