Задача: 1178. Number of Valid Words for Each PuzzleHardTopicsHint
Сложность: hard

Относительно заданной строки-головоломки, слово является допустимым, если выполняются оба следующих условия:

Слово содержит первую букву головоломки.
Каждая буква в слове присутствует в головоломке.
Например, если головоломка "abcdefg", то допустимыми словами являются "faced", "cabbage" и "baggage", а недопустимыми словами являются "beefed" (не включает 'a') и "based" (включает 's', которой нет в головоломке).

Верните массив answer, где answer[i] - это количество слов в данном списке слов words, которые допустимы относительно головоломки puzzles[i].

Пример:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"]
Output: [0,1,3,2,0]

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

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

Ставь 👍 и забирай 📚 Базу знаний