aboutsummaryrefslogtreecommitdiff
path: root/find_all_anagrams.c
blob: f5bca21d32be5b1d59213a90a8abeddd2b2403f7 (plain)
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
}