Leetcode 猜字谜

发表于 更新于 分类于 Waline：

昨天是元宵节，leetcode的每日一题也很应景出了一道猜字谜的题目。

既然真正的猜字谜我不擅长，还是来看看这道算法的猜字谜吧。

首先上题目的链接：

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

解题思路

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

  • 首先我们计算出每一个word 对应的集合 Sw，存放在某一「数据结构」中，便于后续操作中的快速查找；

  • 随后我们依次枚举每一个puzzle，计算出其对应的集合 Sp，并枚举满足要求的子集 S’p。对于每一个 S’p，我们在「数据结构」中查找其出现的次数，那么所有的 S’p出现次数之和就是puzzle 对应的谜底个数。

有了这个方案我们就可以思考如何设计这个数据结构，让我们能快速的存储和查找。

二进制状态压缩

状态压缩

由于题目中规定word 和puzzle 均只包含小写字母，因此 Sw和 Sp的大小最多为 26，我们可以考虑使用一个长度为 26的二进制数 bw或 bp 来表示这一集合。

为什么叫状态压缩呢？其实这个数据结构我们也可以用一个长度为26的数组来表示，但是这样就需要26个Number的空间，但是如果我们用一个Number的二进制形式来表示26个字母是否出现，就可以省下26倍的空间。

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
const freq = new Map();

for(const word of words) {
    let mask = 0;
    for(const ch of word) {
        mask |= (1 << (ch.charCodeAt() - 'a'.charCodeAt()));
    }
    if (CountOne(mask) <= 7) {
        freq.set(mask, (freq.get(mask) || 0) + 1);
    }
}

每次循环中的mask就是压缩后的二进制数，CountOne的作用是返回mask转换为二进制后1的数量

因为每个puzzle长度都为7，所以只有mask中1的数量不超过7的时候才有可能有答案。

二进制遍历

接下来我们要对每个puzzle也进行二进制的状态压缩，计算每个puzzle的状态，然后遍历每个状态的子集，看看freq中有几个相同的。

枚举二进制的伪代码

1
2
3
4
5
6
7
8
9
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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for(const puzzle of puzzles) {
    let total = 0;

    let mask = 0;
    for(let i = 1; i < 7; i++) { //注意，这里从第二位开始，因为第一位是必须有的
        mask |= (1 << (puzzle[i].charCodeAt() - 'a'.charCodeAt()));
    }

    let subset = mask;
    while(subset) {
        // 后6位的子集，然后补上第一位
        let s = subset | (1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()));
        if (freq.has(s)) {
            total += freq.get(s);
        }
        subset = (subset - 1) & mask;
    }

    //上面的循环会漏掉后六位的空集
    if (freq.has(1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()))) {
        total += freq.get(1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()));
    }
    ans.push(total);
}

完整代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * @param {string[]} words
 * @param {string[]} puzzles
 * @return {number[]}
 */
function CountOne(n) {
    const str = n.toString(2);
    let count = 0;
    for (const ch of str) {
        if (parseInt(ch) === 1) {
            count++;
        }
    }
    return count;
}

var findNumOfValidWords = function(words, puzzles) {
    const freq = new Map();

    for(const word of words) {
        let mask = 0;
        for(const ch of word) {
            mask |= (1 << (ch.charCodeAt() - 'a'.charCodeAt()));
        }
        if (CountOne(mask) <= 7) {
            freq.set(mask, (freq.get(mask) || 0) + 1);
        }
    }

    const ans = [];

    for(const puzzle of puzzles) {
        let total = 0;

        let mask = 0;
        for(let i = 1; i < 7; i++) {
            mask |= (1 << (puzzle[i].charCodeAt() - 'a'.charCodeAt()));
        }

        let subset = mask;
        while(subset) {
            let s = subset | (1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()));
            if (freq.has(s)) {
                total += freq.get(s);
            }
            subset = (subset - 1) & mask;
        }

        if (freq.has(1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()))) {
            total += freq.get(1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()));
        }
        ans.push(total);
    }

    return ans;
};