Задача: 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⃣Вычислите суммарную оценку для каждой допустимой комбинации слов и сохраните максимальную оценку.

😎 Решение:

var maxScoreWords = function(words, letters, score) {
    const wordScore = word => word.split('').reduce((acc, ch) => acc + score[ch.charCodeAt(0) - 'a'.charCodeAt(0)], 0);
    const canFormWord = (word, letterCount) => {
        const wordCount = {};
        for (const ch of word) {
            wordCount[ch] = (wordCount[ch] || 0) + 1;
            if (wordCount[ch] > (letterCount[ch] || 0)) {
                return false;
            }
        }
        return true;
    };

    let maxScore = 0;
    const letterCount = {};
    for (const ch of letters) {
        letterCount[ch] = (letterCount[ch] || 0) + 1;
    }

    const n = words.length;
    for (let i = 1; i < (1 << n); i++) {
        let currScore = 0;
        const usedLetters = {};
        let valid = true;
        for (let j = 0; j < n; j++) {
            if (i & (1 << j)) {
                const word = words[j];
                if (canFormWord(word, {...letterCount, ...usedLetters})) {
                    for (const ch of word) {
                        usedLetters[ch] = (usedLetters[ch] || 0) + 1;
                    }
                    currScore += wordScore(word);
                } else {
                    valid = false;
                    break;
                }
            }
        }
        if (valid) {
            maxScore = Math.max(maxScore, currScore);
        }
    }

    return maxScore;
};

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