闲话

继情人节特供 “情侣牵手” 之后，元宵节特供了猜字谜

我们力扣是不可战胜的

题目一开始想的是简单的模拟，循环，但是想到了困难难度，加上是字符串的数组，时间复杂度用脚趾想也有问题。不过还是试了试

代码：

  1. #include<vector>
  2. #include<string>
  3. using namespace std;
  5. class Node {
  6.     public:
  7.     char f;
  8.     bool* p;
  9.     Node() {
  10.         f = '\0';
  11.         p = new bool[26];
  12.         for(int i = 0; i < 26; i++) {
  13.             p[i] = false;
  14.         }
  15.     }
  16. };
  18. class Solution {
  19. public:
  20.     vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
  21.         // vector<Node> nodes;
  22.         vector<int> res;
  23.         for(int i = 0; i < puzzles.size(); i++) {
  24.             int r = 0;
  25.             Node temp;
  26.             temp.f = puzzles[i][0];
  27.             for(int j = 0; puzzles[i][j]; j++) {
  28.                 temp.p[puzzles[i][j]-'a'] = true;
  29.             }
  30.             for(int j = 0; j < words.size(); j++) {
  31.                 bool flag1 = false, flag2 = true;
  32.                 for(int t = 0; words[j][t]; t++) {
  33.                     if(words[j][t] == temp.f) flag1 = true;
  34.                     if(!temp.p[words[j][t]-'a']) {
  35.                         flag2 = false;
  36.                         break;
  37.                     }
  38.                 }
  39.                 if(flag1 && flag2) r++; 
  40.             }
  41.             res.push_back(r);
  42.         }
  43.         return res;
  44.     }
  45. };

就是简单的判断有没有第一个字符和记录每个字符之后比较。出乎意料的是，居然过了九个点
~~
之后是题解：

题目描述

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。

字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：

  • 单词 word 中包含谜面 puzzle 的第一个字母。
  • 单词 word 中的每一个字母都可以在谜面 puzzle 中找到。

例如，如果字谜的谜面是 “abcdefg”，那么可以作为谜底的单词有 “faced”, “cabbage”, 和 “baggage”；而 “beefed”（不含字母 “a”）以及 “based”（其中的 “s” 没有出现在谜面中）则不行。

返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。

输入输出样例

  1. 输入：
  2. words = ["aaaa","asas","able","ability","actt","actor","access"], 
  3. puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
  4. 输出：[1,1,3,2,4,0]
  5. 解释：
  6. 1 个单词可以作为 "aboveyz" 的谜底 : "aaaa" 
  7. 1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
  8. 3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
  9. 2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
  10. 4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"
  11. 没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 'g'。

提示

  • 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] 都是小写英文字母。
  • 每个 puzzles[i] 所包含的字符都不重复。

思路

我们可以设计出解决该字谜问题的一个算法流程：

  • 计算出每个 word 对应的集合 状态压缩和字典树 - 图1 ，存放在某一 数据结构 中，便于后续查找。
  • 枚举 puzzle 对应的集合 状态压缩和字典树 - 图2 并枚举满足要求的子集 状态压缩和字典树 - 图3 ，之后在 数据结构 中查找该子集出现次数，即为所求答案次数

其中的 数据结构 有很多选择，以下介绍两种：

二进制状态压缩

使用一个26位的二进制数来表示组合（因为只有小写字母），从低到高的第 i 个二进制位，表示第 i 个英文字母（i 从 0 开始）

因此我们可以使用一个哈希映射来表示需要的「数据结构」：对于哈希映射中的每一个键值对，其中的键表示一个长度为 26 的二进制数，值表示其出现的次数

即数组 words 中多少个 word 压缩成的二进制数等于键。构造哈希映射的过程也很简单：我们只需要遍历每一个 word，并遍历 word 中的每一个字母，将对应位置的二进制位标记为 1，这样就计算出了 word 对应的二进制表示，将其在哈希映射中作为键对应的值增加 1 即可。

对于 puzzle 也采用同样方法转换即可。

枚举二进制子集也有许多方法，这里介绍两种：

  • 第一种：由于题目中规定 puzzle 的长度恰好为 7，因此我们可以枚举所有 6 位的二进制数（因为 puzzle 中的首字母必须要出现，因此最高位必须是 1，我们只需要枚举剩余的 6 位就行了）。对于每个枚举出的 6 位二进制数，我们遍历 puzzle 中除了首字母以外的其余 6 个字母，只有当二进制位为 1 时，我们才将 puzzle 中的字母在二进制表示中的二进制位标记位 1。这样我们就得到了每一个 puzzle 的子集二进制表示
  • 我们也可以使用通用的「枚举二进制子集」的方法，下面给出伪代码：
    function get_subset(bitmask)
  subset = bitmask
  answer = [bitmask]
  while subset != 0
      subset = (subset - 1) & bitmask
      put subset into the answer list
  end while
  return answer
end function
    其中 bitmask 表示一个二进制数，subset 会遍历所有 bitmask 的子集，并将所有的子集放入 answer 中。需要注意的是，bitmask 本身也是 bitmask 的一个子集，因此 answer 在初始时就包含 bitmask 本身。

与第一种方法类似，我们需要保证 puzzle 中的首字母必须要出现，因此在使用第二种方法枚举子集时，我们先将首字母对应的二进制位标记为 0，每枚举到一个子集，就将首字母对应的二进制位标记为 1，这样得到的子集都是满足要求的。

在得到了子集之后，即可累加出现次数，即为答案。

代码实现

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;
    }
};

第二种方法之后更新

题解参考自力扣