The title

portal

The text

Foreign friends designed an English version of the Chinese puzzle puzzle game, please guess.

The puzzle is given as a string, and a word word counts as a puzzle if it meets two of the following criteria:

The word word contains the first letter of the puzzle. Every letter of the word word can be found in puzzle. For example, if the answer to a puzzle is "abcdefg", the words "faced", "cabbage", and "baggage" would be the answer; There's "beefed" (without the "A") and "based" (with an "S" that's not in the answer).Copy the code

Return an array of answers in which answer[I] is the number of words corresponding to the puzzles[I] in the given word list words.

Example:

Input:

words = [“aaaa”,”asas”,”able”,”ability”,”actt”,”actor”,”access”], Puzzles = [“aboveyz”,”abrodyz”,”abslute”,”absoryz”,”actresz”,”gaswxyz”] output: [1,1,3,2,4,0] “Aaaa” 1 word for “abrodyz” : “Aaaa” 3 words for “abslute” : “Aaaa “, “asas”, “able” 2 for “absoryz” : The 4 words “aAAA “, “asas” are good answers to “actresz” :” aAAA “, “asas”, “ACtt “, “access” are not good answers to “gaswxyz” since none of the words in the list contain the letter ‘G’.

Tip:

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] were all lower case letters. Each of the puzzles[I] contained non-repeating characters.Copy the code

Source: LeetCode

The template

* /int* findNumOfValidWords(char ** words, int wordsSize, char ** puzzles, int puzzlesSize, int* returnSize){}Copy the code

The problem solving

Analysis of the

In this case, what is needed is the verification of elements, not the verification of the number of elements, only the verification of the existence of elements can be considered. The connection between the answers is that the letters that make up the answers must exist inside the answers. If there are elements in the check can be added 1 processing to count the number of puzzles can be solved under the corresponding riddle.

Complete source code

Solve the portal

struct unordered_map {
    int key, val;
    UT_hash_handle hh;
};

int* findNumOfValidWords(char** words, int wordsSize, char** puzzles, int puzzlesSize, int* returnSize) {
    struct unordered_map* frequency = NULL;

    for (int i = 0; i < wordsSize; i++) {
        int n = strlen(words[i]);
        int mask = 0;
        for (int j = 0; j < n; j++) {
            mask |= (1 << (words[i][j] - 'a'));
        }
        if (__builtin_popcount(mask) <= 7) {
            struct unordered_map* tmp;
            HASH_FIND_INT(frequency, &mask, tmp);
            if (tmp == NULL) {
                tmp = malloc(sizeof(struct unordered_map));
                tmp->key = mask;
                tmp->val = 1;
                HASH_ADD_INT(frequency, key, tmp);
            } else{ tmp->val++; }}}int* ans = malloc(sizeof(int) * puzzlesSize);
    *returnSize = 0;

    for (int i = 0; i < puzzlesSize; i++) {
        int total = 0;

        // Enumerate subset method one
        // for (int choose = 0; choose < (1 << 6); ++choose) {
        // int mask = 0;
        // for (int j = 0; j < 6; ++j) {
        // if (choose & (1 << j)) {
        // mask |= (1 << (puzzles[i][j + 1] - 'a'));
        / /}
        / /}
        // mask |= (1 << (puzzles[i][0] - 'a'));
        // struct unordered_map* tmp;
        // HASH_FIND_INT(frequency, &mask, tmp);
        // if (tmp ! = NULL) {
        // total += tmp->val;
        / /}
        // }

        // enumerate subset method 2
        int mask = 0;
        for (int j = 1; j < 7; ++j) {
            mask |= (1 << (puzzles[i][j] - 'a'));
        }
        int subset = mask;
        do {
            int s = subset | (1 << (puzzles[i][0] - 'a'));
            struct unordered_map* tmp;
            HASH_FIND_INT(frequency, &s, tmp);
            if(tmp ! =NULL) {
                total += tmp->val;
            }
            subset = (subset - 1) & mask;
        } while(subset ! = mask); ans[(*returnSize)++] = total; }return ans;
}
Copy the code

Author: LeetCode – Solution

The results