1178. Number of Valid Words for Each Puzzle(Leetcode每日一题-2021.02.26)--抄答案

本文主要是介绍1178. Number of Valid Words for Each Puzzle(Leetcode每日一题-2021.02.26)--抄答案，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

word contains the first letter of puzzle.
For each letter in word, that letter is in puzzle.
For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

Constraints:

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] are English lowercase letters.
Each puzzles[i] doesn’t contain repeated characters.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Example

Input:
words = [“aaaa”,“asas”,“able”,“ability”,“actt”,“actor”,“access”],
puzzles = [“aboveyz”,“abrodyz”,“abslute”,“absoryz”,“actresz”,“gaswxyz”]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for “aboveyz” : “aaaa”
1 valid word for “abrodyz” : “aaaa”
3 valid words for “abslute” : “aaaa”, “asas”, “able”
2 valid words for “absoryz” : “aaaa”, “asas”
4 valid words for “actresz” : “aaaa”, “asas”, “actt”, “access”
There’re no valid words for “gaswxyz” cause none of the words in the list contains letter ‘g’.

Solution

class Solution {
public:vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {unordered_map<int, int> frequency;for (const string& word: words) {int mask = 0;for (char ch: word) {mask |= (1 << (ch - 'a'));}if (__builtin_popcount(mask) <= 7) {++frequency[mask];}}vector<int> ans;for (const string& puzzle: puzzles) {int total = 0;// 枚举子集方法一// for (int choose = 0; choose < (1 << 6); ++choose) {//     int mask = 0;//     for (int i = 0; i < 6; ++i) {//         if (choose & (1 << i)) {//             mask |= (1 << (puzzle[i + 1] - 'a'));//         }//     }//     mask |= (1 << (puzzle[0] - 'a'));//     if (frequency.count(mask)) {//         total += frequency[mask];//     }// }// 枚举子集方法二int mask = 0;for (int i = 1; i < 7; ++i) {mask |= (1 << (puzzle[i] - 'a'));}int subset = mask;do {int s = subset | (1 << (puzzle[0] - 'a'));if (frequency.count(s)) {total += frequency[s];}subset = (subset - 1) & mask;} while (subset != mask);ans.push_back(total);}return ans;}
};//作者：LeetCode-Solution
//链接：https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/solution/cai-zi-mi-by-leetcode-solution-345u/