Задача: 1255. Maximum Score Words Formed by Letters
Сложность: hard

Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.

Пример:

Input: words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
Output: 23

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

1⃣Создайте функцию для вычисления оценки слова.

2⃣Используйте метод перебора подмножеств (или битовое представление всех подмножеств) для нахождения всех возможных комбинаций слов.
Для каждой комбинации проверяйте, можно ли составить каждое слово из доступных букв.

3⃣Вычислите суммарную оценку для каждой допустимой комбинации слов и сохраните максимальную оценку.

😎 Решение:

class Solution {
    function maxScoreWords($words, $letters, $score) {
        $letterCount = array_count_values($letters);
        $maxScore = 0;
        
        $n = count($words);
        for ($i = 1; $i < (1 << $n); $i++) {
            $currScore = 0;
            $usedLetters = [];
            $valid = true;
            for ($j = 0; $j < $n; $j++) {
                if ($i & (1 << $j)) {
                    foreach (str_split($words[$j]) as $ch) {
                        if (isset($usedLetters[$ch])) {
                            $usedLetters[$ch]++;
                        } else {
                            $usedLetters[$ch] = 1;
                        }
                        if (!isset($letterCount[$ch]) || $usedLetters[$ch] > $letterCount[$ch]) {
                            $valid = false;
                            break;
                        }
                        $currScore += $score[ord($ch) - ord('a')];
                    }
                }
                if (!$valid) break;
            }
            if ($valid) {
                $maxScore = max($maxScore, $currScore);
            }
        }

        return $maxScore;
    }
}

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