題目

https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/

題解

看了答案，堪稱力扣最詳細的答案，從時間復雜度的角度分析本題解法：

https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/solution/

其中，有一個重要的 trick（不是很懂，但很實用）

Here we find another challenge: How to iterate over all the subsets of a set? This is a classic problem that can be solved using a depth-first search.

However, when working with a bitmask that represents a set of all possible items, we can use a simple trick to find all possible subsets of those items using only a for loop.

Let’s have a quick look at how this works. The pseudo-code is as follows:

for (subset = bitmask; subsets >= 0; subset = (subset - 1) & bitmask) {// do what you want with the current subset... }

Or with a while loop:

let subset = bitmask; while (subsets >= 0) {// do what you want with the current subset...subset = (subset - 1) & bitmask; }

Why does this work? The subsets must be included in range [0, bitmask], and if we iterate from bitmask to 0 one by one, we are guaranteed to visit the bitmask of every subset along the way.

But we can also meet those that are not a subset of bitmask. Fortunately, instead of decrementing subset by one at each iteration, we can use subset = (subset - 1) & bitmask to ensure that each subset only contains characters that exist in bitmask.

Also, we will not miss any subset because subset - 1 turns at most one 1 into 0.

代碼

class Solution {public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {// 對于每一個puzzle，求滿足條件的word的個數。// 條件：// 1. puzzle包含word的所有字母// 2. word包含puzzle的第一個字母Map<Integer, Integer> map = new HashMap<>();for (String word : words) {int bitmask = 0;for (int i = 0; i < word.length(); i++) {bitmask |= 1 << word.charAt(i) - 'a';}map.put(bitmask, map.getOrDefault(bitmask, 0) + 1);}List<Integer> result = new ArrayList<>();for (String puzzle : puzzles) {int bitmask = 0;for (int i = 0; i < puzzle.length(); i++) { bitmask |= 1 << puzzle.charAt(i) - 'a';}int first = 1 << puzzle.charAt(0) - 'a';int count = map.getOrDefault(first, 0);bitmask &= ~first;// all subsets of bitmask, trickfor (int subMask = bitmask; subMask > 0; subMask = (subMask - 1) & bitmask) {count += map.getOrDefault(subMask | first, 0);}result.add(count);}return result;} }

總結

以上是生活随笔為你收集整理的leetcode 1178. Number of Valid Words for Each Puzzle | 1178. 猜字谜（bitmask位运算）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。