1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
// 438. Find All Anagrams in a String
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
* given two strings 's & p', return an array of all the start indices of 'p's
* anagrams in 's' (any order). an anagram is a word or phrase formed by
* rearranging the letters of a different word or phrase, typically using all
* original letters exactly one
*/
int cmp(int *a, int *b) {
for (int i = 0; i < 26; i++)
if (a[i] != b[i])
return 0;
return 1;
}
int *findAnagrams(char *s, char *p, int *returnSize) {
int ssz = strlen(s), psz = strlen(p);
int *ans = (int *)malloc(sizeof(int) * ssz);
if (ssz < psz)
return ans;
int sabc[26] = {0}, pabc[26] = {0};
(*returnSize) = 0;
for (int i = 0; i < psz; i++) {
pabc[p[i] - 'a']++;
sabc[s[i] - 'a']++;
}
for (int i = 0; i < ssz - psz; i++) {
if (i != 0)
sabc[s[i + psz - 1] - 'a']++;
if (cmp(sabc, pabc)) {
ans[*returnSize] = i;
(*returnSize)++;
}
sabc[s[i] - 'a']--;
}
return ans;
}
int main() {
char s1[] = "cbaebabacd", s2[] = "abc";
char p1[] = "abc", p2[] = "ab";
int rs1[] = {2}, rs2[] = {3};
printf("%d\n", *findAnagrams(s2, p1, rs1)); // expect: 0 6
printf("%d\n", *findAnagrams(s2, p2, rs2)); // expect: 0 1 2
}
|