Задача: 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⃣Для каждой подмаски увеличивайте счетчик на количество слов, соответствующих подмаске. Мы можем найти количество слов, соответствующих подмаске, используя карту, построенную на предыдущем шаге.

😎 Решение:

class Solution {
    private function bitmask($word) {
        $mask = 0;
        for ($i = 0; $i < strlen($word); $i++) {
            $mask |= 1 << (ord($word[$i]) - ord('a'));
        }
        return $mask;
    }

    function findNumOfValidWords($words, $puzzles) {
        $wordCount = [];
        foreach ($words as $word) {
            $mask = $this->bitmask($word);
            if (!isset($wordCount[$mask])) {
                $wordCount[$mask] = 0;
            }
            $wordCount[$mask]++;
        }

        $result = [];
        foreach ($puzzles as $puzzle) {
            $first = 1 << (ord($puzzle[0]) - ord('a'));
            $count = isset($wordCount[$first]) ? $wordCount[$first] : 0;
            $mask = $this->bitmask(substr($puzzle, 1));
            for ($submask = $mask; $submask > 0; $submask = ($submask - 1) & $mask) {
                $count += isset($wordCount[$submask | $first]) ? $wordCount[$submask | $first] : 0;
            }
            $result[] = $count;
        }
        return $result;
    }
}

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