aboutsummaryrefslogtreecommitdiff
path: root/word_subsets.cpp
blob: ea4c1f9e4513ae2583b5a2323fed4153034add23 (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
#include "leetcode.h"

class Solution {
public:
  vector<string> wordSubsets(vector<string> &words1, vector<string> &words2) {
    int bFreq[26] = {0}, check[26] = {0};
    int cMax = 0;
    vector<string> ans;
    for (string word : words2) {
      for (char c : word)
        check[c - 'a']++;
      for (int j = 0; j < 26; j++) {
        int diff = check[j] - bFreq[j];
        if (diff > 0)
          cMax += diff, bFreq[j] += diff;
      }
      if (cMax > 10)
        return ans;
      fill(check, check + 26, 0);
    }
    for (string word : words1) {
      int j;
      for (char c : word)
        check[c - 'a']++;
      for (j = 0; j < 26; j++)
        if (check[j] < bFreq[j])
          break;
      if (j == 26)
        ans.push_back(word);
      fill(check, check + 26, 0);
    }
    return ans;
  }
};