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

class Solution {
public:
  vector<int> findNumOfValidWords(vector<string> &words,
                                  vector<string> &puzzles) {
    unordered_map<int, int> um;
    for (auto w : words)
      um[(mask(w))]++;
    vector<int> ans;
    for (auto p : puzzles) {
      int m = mask(p), s = m, first = (1 << p[0] - 'a'), curr = 0;
      while (s) {
        if (s & first)
          curr += um[s];
        s = (s - 1) & m;
      }
      ans.push_back(curr);
    }
    return ans;
  }

private:
  int mask(string word) {
    int m = 0;
    for (auto w : word)
      m |= (1 << w - 'a');
    return m;
  }
};

int main() {
  Solution obj;
  vector<string> words = {"aaaa", "asas",  "able",  "ability",
                          "actt", "actor", "access"};
  vector<string> puzzles = {"aboveyz", "abrodyz", "abslute",
                            "absoryz", "actresz", "gaswxyz"};
  for (const auto &i : obj.findNumOfValidWords(words, puzzles))
    cout << i << endl;
}