Skip to content

1178. Number of Valid Words for Each Puzzle 👍

  • Time:
  • Space: 
 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
class Solution {
 public:
  vector<int> findNumOfValidWords(vector<string>& words,
                                  vector<string>& puzzles) {
    vector<int> ans;
    unordered_map<int, int> binaryCount;

    for (const string& word : words) {
      int mask = 0;
      for (char c : word)
        mask |= 1 << c - 'a';
      ++binaryCount[mask];
    }

    for (const string& puzzle : puzzles) {
      int valid = 0;
      const int n = puzzle.length() - 1;
      for (int i = 0; i < (1 << n); ++i) {
        int mask = 1 << puzzle[0] - 'a';
        for (int j = 0; j < n; ++j)
          if (i >> j & 1)
            mask |= 1 << puzzle[j + 1] - 'a';
        if (const auto it = binaryCount.find(mask); it != binaryCount.cend())
          valid += it->second;
      }
      ans.push_back(valid);
    }

    return ans;
  }
};

 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
class Solution {
  public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
    List<Integer> ans = new ArrayList<>();
    Map<Integer, Integer> binaryCount = new HashMap<>();

    for (final String word : words) {
      int mask = 0;
      for (char c : word.toCharArray())
        mask |= 1 << (c - 'a');
      binaryCount.merge(mask, 1, Integer::sum);
    }

    for (final String puzzle : puzzles) {
      int valid = 0;
      final int n = puzzle.length() - 1;
      for (int i = 0; i < (1 << n); ++i) {
        int mask = 1 << puzzle.charAt(0) - 'a';
        for (int j = 0; j < n; ++j)
          if ((i >> j & 1) == 1)
            mask |= 1 << puzzle.charAt(j + 1) - 'a';
        if (binaryCount.containsKey(mask))
          valid += binaryCount.get(mask);
      }
      ans.add(valid);
    }

    return ans;
  }
}

 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
class Solution:
  def findNumOfValidWords(
      self,
      words: list[str],
      puzzles: list[str],
  ) -> list[int]:
    ans = []
    binaryCount = collections.Counter()

    for word in words:
      mask = 0
      for c in word:
        mask |= 1 << string.ascii_lowercase.index(c)
      binaryCount[mask] += 1

    for puzzle in puzzles:
      valid = 0
      n = len(puzzle) - 1
      for i in range(1 << n):
        mask = 1 << ord(puzzle[0]) - ord('a')
        for j in range(n):
          if i >> j & 1:
            mask |= 1 << ord(puzzle[j + 1]) - ord('a')
        if mask in binaryCount:
          valid += binaryCount[mask]
      ans.append(valid)

    return ans