Leetcode Puzzle

Yesterday was the Lantern Festival, and leetcode’s daily question also came up with a question to guess the word puzzle.

Since I’m not good at real charades, let’s take a look at this algorithm’s charade.

First, the link to the topic:

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

Problem-solving ideas

We can design an algorithm to solve this puzzle problem.

• First, we calculate the set Sw corresponding to each word and store it in a “data structure” for quick search in subsequent operations;

• Then we enumerate each puzzle in turn, calculate its corresponding set Sp, and enumerate the subset S’p that meets the requirements. For each S’p, we look up the number of occurrences in the “data structure”, then the sum of the occurrences of all S’ps is the number of puzzles corresponding to the puzzle.

With this solution, we can think about how to design this data structure, so that we can quickly store and search.

Binary state compression

State compression

Since the title specifies that both word and puzzle contain only lowercase letters, the size of Sw and Sp is at most 26. We can consider using a binary number bw or bp of length 26 to represent this set.

Why is it called state compression? In fact, this data structure can also be represented by an array with a length of 26, but this requires the space of 26 Numbers, but if we use the binary form of a Number to represent whether 26 letters appear, we can save 26 times the space.

Therefore, we can use a hash map to represent the required “data structure”: for each Attribute-Value Pair in the hash map, the key represents a binary number of length 26, and the value represents the number of times it appears, that is, how many words in the array of words are compressed into binary numbers equal to the key. The process of constructing a hash map is also very simple: we just need to traverse each word and traverse each letter in the word, marking the binary bit of the corresponding position as 1, so that the binary representation of the word is calculated, and it is added to the hash map. The value corresponding to the key in the hash map can be incremented by 1.

The code is as follows:

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

The mask in each loop is the compressed binary number. The function of CountOne is to return the number of 1s after the mask is converted to binary

Because each puzzle is 7 in length, the answer is only possible if the number of 1s in the mask does not exceed 7.

Binary traversal

Next we need to perform binary state compression on each puzzle as well, calculate the state of each puzzle, and then traverse a subset of each state to see how many are the same in freq.

Enumerate binary pseudocode

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

The code is as follows:

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

    let mask = 0;
    For (let i = 1; i < 7; i ++) { // note that this starts with the second digit, because the first digit is required
        mask |= (1 << (puzzle[i].charCodeAt() - 'a'.charCodeAt()));
    }

    let subset = mask;
    while(subset) {
        Subset of the last 6 digits, then add the first digit
        let s = subset | (1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()));
        if (freq.has(s)) {
            total += freq.get(s);
        }
        subset = (subset - 1) & mask;
    }

    //The above loop will miss the last six bits of the empty set
    if (freq.has(1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()))) {
        total += freq.get(1 << (puzzle[0].charCodeAt() - 'a'.charCodeAt()));
    }
    ans.push(total);
}

Complete code

/**
 * @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;
};