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 & 1 << j)
            mask |= 1 << puzzle[j + 1] - 'a';
        if (binaryCount.count(mask))
          valid += binaryCount[mask];
      }
      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.put(mask, binaryCount.getOrDefault(mask, 0) + 1);
    }

    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 & 1 << j) > 0)
            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
class Solution:
  def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
    ans = []
    binaryCount = Counter()

    for word in words:
      mask = 0
      for c in word:
        mask |= 1 << (ord(c) - ord('a'))
      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 & 1 << j:
            mask |= 1 << ord(puzzle[j + 1]) - ord('a')
        if mask in binaryCount:
          valid += binaryCount[mask]
      ans.append(valid)

    return ans