Задача: 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 {
    func maxScoreWords(_ words: [String], _ letters: [Character], _ score: [Int]) -> Int {
        var letterCount = [Character: Int]()
        for ch in letters {
            letterCount[ch, default: 0] += 1
        }

        func wordScore(_ word: String) -> Int {
            var total = 0
            for ch in word {
                total += score[Int(ch.asciiValue! - Character("a").asciiValue!)]
            }
            return total
        }

        func canFormWord(_ word: String, _ letterCount: [Character: Int]) -> Bool {
            var count = [Character: Int]()
            for ch in word {
                count[ch, default: 0] += 1
                if count[ch]! > letterCount[ch, default: 0] {
                    return false
                }
            }
            return true
        }

        var maxScore = 0
        let n = words.count
        for i in 1..<1<<n {
            var currScore = 0
            var usedLetters = [Character: Int]()
            var valid = true
            for j in 0..<n {
                if (i & 1<<j) != 0 {
                    let word = words[j]
                    if canFormWord(word, letterCount) {
                        currScore += wordScore(word)
                        for ch in word {
                            usedLetters[ch, default: 0] += 1
                        }
                    } else {
                        valid = false
                        break
                    }
                }
            }
            if valid {
                maxScore = max(maxScore, currScore)
            }
        }

        return maxScore
    }
}

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