aboutsummaryrefslogtreecommitdiff
path: root/word_subsets.c
blob: 72e7adf434044e89f5a1351fb6ae780eab81d8ff (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
50
51
52
53
54
55
56
57
// 916. Word Subsets
#include "leetcode.h"

/*
 * you are given two string arrays 'words1' and 'words2'. a string 'b' is a
 * subset of string 'a' if every letter in 'b' occurs in 'a' including
 * multiplicity. a string 'a' from 'words1' is universal if for every string 'b'
 * in 'words2', 'b' is a subset of 'a'. return an array of all the universal
 * strins in 'words1'. you may return the answer in any order.
 */

char **wordSubsets(char **words1, int words1Size, char **words2, int words2Size,
                   int *returnSize) {
  int max_freq[26] = {0}, tmp_freq[26];
  for (int i = 0; i < words2Size; ++i) {
    memset(tmp_freq, 0, sizeof(tmp_freq));
    for (int j = 0; words2[i][j] != '\0'; ++j)
      tmp_freq[words2[i][j] - 'a']++;
    for (int j = 0; j < 26; ++j)
      max_freq[j] = fmax(max_freq[j], tmp_freq[j]);
  }
  char **ans = (char **)malloc(words1Size * sizeof(char *));
  *returnSize = 0;
  for (int i = 0; i < words1Size; ++i) {
    memset(tmp_freq, 0, sizeof(tmp_freq));
    for (int j = 0; words1[i][j] != '\0'; ++j)
      tmp_freq[words1[i][j] - 'a']++;
    bool universal = true;
    for (int j = 0; j < 26; ++j)
      if (max_freq[j] > tmp_freq[j]) {
        universal = false;
        break;
      }
    if (universal)
      ans[(*returnSize)++] = words1[i];
  }
  return ans;
}

int main() {
  char *w11[] = {"amazon", "apple", "facebook", "google", "leetcode"},
       *w21[] = {"e", "o"};
  char *w12[] = {"amazon", "apple", "facebook", "google", "leetcode"},
       *w22[] = {"l", "e"};
  int rs1, rs2;
  char **ws1 = wordSubsets((char **)w11, ARRAY_SIZE(w11), (char **)w21,
                           ARRAY_SIZE(w21), &rs1);
  char **ws2 = wordSubsets((char **)w12, ARRAY_SIZE(w12), (char **)w22,
                           ARRAY_SIZE(w22), &rs2);
  for (int i = 0; i < rs1; i++)
    printf("%s ", ws1[i]); // expect: ["facebook","google","leetcode"]
  printf("\n");
  for (int i = 0; i < rs2; i++)
    printf("%s ", ws2[i]); // expect: ["apple","google","leetcode"]
  printf("\n");
  free(ws1), free(ws2);
}