1178. Number of Valid Words for Each PuzzleHardTopicsHint

public class Solution {
    private int Bitmask(string word) {
        int mask = 0;
        foreach (char letter in word) {
            mask |= 1 << (letter - 'a');
        }
        return mask;
    }
    public IList<int> FindNumOfValidWords(string[] words, string[] puzzles) {
        var wordCount = new Dictionary<int, int>();
        foreach (var word in words) {
            int mask = Bitmask(word);
            if (!wordCount.ContainsKey(mask)) {
                wordCount[mask] = 0;
            }
            wordCount[mask]++;
        }
        var result = new List<int>();
        foreach (var puzzle in puzzles) {
            int first = 1 << (puzzle[0] - 'a');
            int count = wordCount.ContainsKey(first) ? wordCount[first] : 0;
            int mask = Bitmask(puzzle.Substring(1));
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                count += wordCount.ContainsKey(submask | first) ? wordCount[submask | first] : 0;
            }
            result.Add(count);
        }
        return result;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private int Bitmask(string word) {
        int mask = 0;
        foreach (char letter in word) {
            mask |= 1 << (letter - 'a');
        }
        return mask;
    }
    public vector<int> FindNumOfValidWords(vector<string> words, vector<string> puzzles) {
        var wordCount = new unordered_map<int, int>();
        foreach (var word in words) {
            int mask = Bitmask(word);
            if (!wordCount.count(mask)) {
                wordCount[mask] = 0;
            }
            wordCount[mask]++;
        }
        var result = new List<int>();
        foreach (var puzzle in puzzles) {
            int first = 1 << (puzzle[0] - 'a');
            int count = wordCount.count(first) ? wordCount[first] : 0;
            int mask = Bitmask(puzzle.Substring(1));
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                count += wordCount.count(submask | first) ? wordCount[submask | first] : 0;
            }
            result.push_back(count);
        }
        return result;
    }
}

class Solution {
    private int bitmask(String word) {
        int mask = 0;
        for (char letter : word.toCharArray()) {
            mask |= 1 << (letter - 'a');
        }
        return mask;
    }

    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer, Integer> wordCount = new HashMap<>();
        for (String word : words) {
            int mask = bitmask(word);
            wordCount.put(mask, wordCount.getOrDefault(mask, 0) + 1);
        }

        List<Integer> result = new ArrayList<>();
        for (String puzzle : puzzles) {
            int first = 1 << (puzzle.charAt(0) - 'a');
            int count = wordCount.getOrDefault(first, 0);
            int mask = bitmask(puzzle.substring(1));
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                count += wordCount.getOrDefault(submask | first, 0);
            }
            result.add(count);
        }
        return result;
    }
}

var bitmask = function(word) {
    let mask = 0;
    for (let letter of word) {
        mask |= 1 << (letter.charCodeAt(0) - 'a'.charCodeAt(0));
    }
    return mask;
};

var findNumOfValidWords = function(words, puzzles) {
    let wordCount = new Map();
    for (let word of words) {
        let mask = bitmask(word);
        wordCount.set(mask, (wordCount.get(mask) || 0) + 1);
    }

    let result = [];
    for (let puzzle of puzzles) {
        let first = 1 << (puzzle[0].charCodeAt(0) - 'a'.charCodeAt(0));
        let count = wordCount.get(first) || 0;
        let mask = bitmask(puzzle.slice(1));
        for (let submask = mask; submask > 0; submask = (submask - 1) & mask) {
            count += wordCount.get(submask | first) || 0;
        }
        result.push(count);
    }
    return result;
};

class Solution:
    def bitmask(self, word: str) -> int:
        mask = 0
        for letter in word:
            mask |= 1 << (ord(letter) - ord('a'))
        return mask

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        word_count = {}
        for word in words:
            mask = self.bitmask(word)
            word_count[mask] = word_count.get(mask, 0) + 1

        result = []
        for puzzle in puzzles:
            first = 1 << (ord(puzzle[0]) - ord('a'))
            count = word_count.get(first, 0)
            mask = self.bitmask(puzzle[1:])
            submask = mask
            while submask > 0:
                count += word_count.get(submask | first, 0)
                submask = (submask - 1) & mask
            result.append(count)
        return result

func bitmask(word string) int {
    mask := 0
    for _, letter := range word {
        mask |= 1 << (letter - 'a')
    }
    return mask
}

func findNumOfValidWords(words []string, puzzles []string) []int {
    wordCount := make(map[int]int)
    for _, word := range words {
        mask := bitmask(word)
        wordCount[mask]++
    }

    result := make([]int, 0, len(puzzles))
    for _, puzzle := range puzzles {
        first := 1 << (puzzle[0] - 'a')
        count := wordCount[first]
        mask := bitmask(puzzle[1:])
        for submask := mask; submask > 0; submask = (submask - 1) & mask {
            count += wordCount[submask | first]
        }
        result = append(result, count)
    }
    return result
}

Algorithm

Постройте карту. Для каждого слова в списке words:

Преобразуйте его в битовую маску его символов. Если эта битовая маска не была ранее встречена, сохраните ее в качестве ключа в карте со значением 1. Если она была ранее встречена, увеличьте счетчик для этой битовой маски на 1.

Подсчитайте количество допустимых слов для каждой головоломки. Для каждой головоломки в списке puzzles:

Преобразуйте ее в битовую маску ее символов. Итерируйте по каждой возможной подмаске, содержащей первую букву головоломки (puzzle[i][0]). Слово является допустимым для головоломки, если его битовая маска совпадает с одной из подмасок головоломки.

Для каждой подмаски увеличивайте счетчик на количество слов, соответствующих подмаске. Мы можем найти количество слов, соответствующих подмаске, используя карту, построенную на предыдущем шаге.

😎