1255. Maximum Score Words Formed by Letters
LeetCode
hard
original: C#
#array
#bit-manipulation
#csharp
#hard
#hash-table
#leetcode
#math
#string
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
given список слов, список отдельных букв (могут повторяться) и оценка каждого символа. return максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (words[i] не может быть использовано два или более раз). Не обязательно использовать все символы в буквах, каждая буква может быть использована только один раз. Оценка букв 'a', 'b', 'c', ... , 'z' задаются значениями score[0], score[1], ... , score[25] соответственно.
Ejemplo:
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# solución
coincidente/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++ solución
borrador automático, revisar antes de enviar#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 solución
coincidente/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 solución
coincidente/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 solución
coincidente/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 solución
coincidente/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
}Algorithm
Создайте функцию для вычисления оценки слова.
Используйте метод перебора подмножеств (или битовое представление всех подмножеств) для нахождения всех возможных комбинаций слов.
Для каждой комбинации проверяйте, можно ли составить каждое слово из доступных букв.
Вычислите суммарную оценку для каждой допустимой комбинации слов и сохраните максимальную оценку.
😎
Vacantes para esta tarea
Se muestran vacantes activas con etiquetas coincidentes.
Todavía no hay vacantes activas.