1255. Maximum Score Words Formed by Letters
LeetCode
hard
original: C#
#array
#bit-manipulation
#csharp
#hard
#hash-table
#leetcode
#math
#string
選択した UI 言語に合わせて問題文をロシア語から翻訳します。コードは変更しません。
given список слов, список отдельных букв (могут повторяться) и оценка каждого символа. return максимальную оценку любого правильного набора слов, образованного с помощью заданных букв (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# 解法
照合済み/オリジナルpublic 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++ 解法
自動ドラフト、提出前に確認#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 解法
照合済み/オリジナルimport 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 解法
照合済み/オリジナル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;
};Python 解法
照合済み/オリジナルfrom 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 解法
照合済み/オリジナルfunc 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
Создайте функцию для вычисления оценки слова.
Используйте метод перебора подмножеств (или битовое представление всех подмножеств) для нахождения всех возможных комбинаций слов.
Для каждой комбинации проверяйте, можно ли составить каждое слово из доступных букв.
Вычислите суммарную оценку для каждой допустимой комбинации слов и сохраните максимальную оценку.
😎
Vacancies for this task
有効な求人 with overlapping task tags are 表示.
有効な求人はまだありません。