题目

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, trick
            for (int subMask = bitmask; subMask > 0; subMask = (subMask - 1) & bitmask) {
                count += map.getOrDefault(subMask | first, 0);
            }
            result.add(count);
        }
        return result;
    }
}