1255. Maximum Score Words Formed by Letters
leetcode hard
#array#bit-manipulation#csharp#hard#hash-table#leetcode#math#string
Task
Даны список слов, список отдельных букв (могут повторяться) и оценка каждого символа. Верните максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (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
C# solution
matched/originalpublic class Solution {
public int MaxScoreWords(string[] words, char[] letters, int[] score) {
Dictionary<char, int> letterCount = new Dictionary<char, int>();
foreach (char ch in letters) {
if (!letterCount.ContainsKey(ch)) {
letterCount[ch] = 0;
}
letterCount[ch]++;
}
int WordScore(string word) {
int total = 0;
foreach (char ch in word) {
total += score[ch - 'a'];
}
return total;
}
bool CanFormWord(string word, Dictionary<char, int> letterCount) {
Dictionary<char, int> count = new Dictionary<char, int>();
foreach (char ch in word) {
if (!count.ContainsKey(ch)) {
count[ch] = 0;
}
count[ch]++;
if (count[ch] > letterCount.GetValueOrDefault(ch, 0)) {
return false;
}
}
return true;
}
int maxScore = 0;
int n = words.Length;
for (int i = 1; i < (1 << n); i++) {
int currScore = 0;
Dictionary<char, int> usedLetters = new Dictionary<char, int>();
bool valid = true;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
string word = words[j];
if (CanFormWord(word, letterCount)) {
currScore += WordScore(word);
foreach (char ch in word) {
if (!usedLetters.ContainsKey(ch)) {
usedLetters[ch] = 0;
}
usedLetters[ch]++;
}
} else {
valid = false;
break;
}
}
}
if (valid) {
maxScore = Math.Max(maxScore, currScore);
}
}
return maxScore;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int MaxScoreWords(vector<string> words, char[] letters, vector<int>& score) {
unordered_map<char, int> letterCount = new unordered_map<char, int>();
foreach (char ch in letters) {
if (!letterCount.count(ch)) {
letterCount[ch] = 0;
}
letterCount[ch]++;
}
int WordScore(string word) {
int total = 0;
foreach (char ch in word) {
total += score[ch - 'a'];
}
return total;
}
bool CanFormWord(string word, unordered_map<char, int> letterCount) {
unordered_map<char, int> count = new unordered_map<char, int>();
foreach (char ch in word) {
if (!count.count(ch)) {
count[ch] = 0;
}
count[ch]++;
if (count[ch] > letterCount.GetValueOrDefault(ch, 0)) {
return false;
}
}
return true;
}
int maxScore = 0;
int n = words.size();
for (int i = 1; i < (1 << n); i++) {
int currScore = 0;
unordered_map<char, int> usedLetters = new unordered_map<char, int>();
bool valid = true;
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
string word = words[j];
if (CanFormWord(word, letterCount)) {
currScore += WordScore(word);
foreach (char ch in word) {
if (!usedLetters.count(ch)) {
usedLetters[ch] = 0;
}
usedLetters[ch]++;
}
} else {
valid = false;
break;
}
}
}
if (valid) {
maxScore = max(maxScore, currScore);
}
}
return maxScore;
}
}Java solution
matched/originalimport java.util.*;
public class Solution {
public int maxScoreWords(String[] words, char[] letters, int[] score) {
int maxScore = 0;
Map<Character, Integer> letterCount = new HashMap<>();
for (char ch : letters) {
letterCount.put(ch, letterCount.getOrDefault(ch, 0) + 1);
}
for (int i = 1; i < (1 << words.length); i++) {
int currScore = 0;
Map<Character, Integer> usedLetters = new HashMap<>();
boolean valid = true;
for (int j = 0; j < words.length; j++) {
if ((i & (1 << j)) != 0) {
for (char ch : words[j].toCharArray()) {
usedLetters.put(ch, usedLetters.getOrDefault(ch, 0) + 1);
if (usedLetters.get(ch) > letterCount.getOrDefault(ch, 0)) {
valid = false;
break;
}
currScore += score[ch - 'a'];
}
}
if (!valid) break;
}
if (valid) {
maxScore = Math.max(maxScore, currScore);
}
}
return maxScore;
}
}JavaScript solution
matched/originalvar 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;
};Python solution
matched/originalfrom collections import Counter
from itertools import combinations
def maxScoreWords(words, letters, score):
def word_score(word):
return sum(score[ord(ch) - ord('a')] for ch in word)
def can_form_word(word, letter_count):
word_count = Counter(word)
for ch in word_count:
if word_count[ch] > letter_count[ch]:
return False
return True
max_score = 0
letter_count = Counter(letters)
for r in range(1, len(words) + 1):
for combo in combinations(words, r):
combo_score = 0
used_letters = Counter()
valid_combo = True
for word in combo:
word_count = Counter(word)
if can_form_word(word, letter_count - used_letters):
combo_score += word_score(word)
used_letters += word_count
else:
valid_combo = False
break
if valid_combo:
max_score = max(max_score, combo_score)
return max_scoreGo solution
matched/originalfunc maxScoreWords(words []string, letters []byte, score []int) int {
letterCount := make(map[byte]int)
for _, ch := range letters {
letterCount[ch]++
}
wordScore := func(word string) int {
total := 0
for i := 0; i < len(word); i++ {
total += score[word[i] - 'a']
}
return total
}
canFormWord := func(word string, letterCount map[byte]int) bool {
count := make(map[byte]int)
for i := 0; i < len(word); i++ {
count[word[i]]++
if count[word[i]] > letterCount[word[i]] {
return false
}
}
return true
}
maxScore := 0
n := len(words)
for i := 1; i < (1 << n); i++ {
currScore := 0
usedLetters := make(map[byte]int)
valid := true
for j := 0; j < n; j++ {
if i & (1 << j) != 0 {
word := words[j]
if canFormWord(word, letterCount) {
currScore += wordScore(word)
for k := 0; k < len(word); k++ {
usedLetters[word[k]]++
}
} else {
valid = false
break
}
}
}
if valid {
if currScore > maxScore {
maxScore = currScore
}
}
}
return maxScore
}Explanation
Algorithm
Создайте функцию для вычисления оценки слова.
Используйте метод перебора подмножеств (или битовое представление всех подмножеств) для нахождения всех возможных комбинаций слов.
Для каждой комбинации проверяйте, можно ли составить каждое слово из доступных букв.
Вычислите суммарную оценку для каждой допустимой комбинации слов и сохраните максимальную оценку.
😎