Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1255.html
1255. Maximum Score Words Formed by Letters
Level
Hard
Description
Given a list of words
, list of single letters
(might be repeating) and score
of every character.
Return the maximum score of any valid set of words formed by using the given letters (words[i]
cannot be used two or more times).
It is not necessary to use all characters in letters
and each letter can only be used once. Score of letters 'a'
, 'b'
, 'c'
, …, 'z'
is given by score[0]
, score[1]
, …, score[25]
respectively.
Example 1:
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
Explanation:
Score a=1, c=9, d=5, g=3, o=2
Given letters, we can form the words “dad” (5+1+5) and “good” (3+2+2+5) with a score of 23.
Words “dad” and “dog” only get a score of 21.
Example 2:
Input: words = [“xxxz”,”ax”,”bx”,”cx”], letters = [“z”,”a”,”b”,”c”,”x”,”x”,”x”], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
Output: 27
Explanation:
Score a=4, b=4, c=4, x=5, z=10
Given letters, we can form the words “ax” (4+5), “bx” (4+5) and “cx” (4+5) with a score of 27.
Word “xxxz” only get a score of 25.
Example 3:
Input: words = [“leetcode”], letters = [“l”,”e”,”t”,”c”,”o”,”d”], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
Output: 0
Explanation:
Letter “e” can only be used once.
Constraints:
1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length == 26
0 <= score[i] <= 10
words[i]
,letters[i]
contains only lower case English letters.
Solution
First, calculate the available numbers of each letter according to letters
. For example, if 'a'
occurs twice in letters
, then the available number of a
is 2.
Then loop over all possible combinations of words
, where each word is selected or not selected. For each combination, if it is possible, which means the selected words can be formed by using the given letters
, then calculate the total score of the combination and maintain the maximum score.
Finally, return the maximum score.
-
class Solution { public int maxScoreWords(String[] words, char[] letters, int[] score) { int maxScore = 0; int[] available = new int[26]; for (char letter : letters) available[letter - 'a']++; int length = words.length; int states = 1 << length; for (int i = 1; i < states; i++) { int[] bits = numToBits(i, length); if (possible(words, bits, available)) { int curScore = calculateScore(words, bits, score); maxScore = Math.max(maxScore, curScore); } } return maxScore; } public int[] numToBits(int num, int length) { int[] bits = new int[length]; for (int i = 0; i < length; i++) { bits[i] = num % 2; num /= 2; if (num == 0) break; } return bits; } public boolean possible(String[] words, int[] bits, int[] available) { int[] counts = new int[26]; int length = words.length; for (int i = 0; i < length; i++) { if (bits[i] == 1) { String word = words[i]; int wordLength = word.length(); for (int j = 0; j < wordLength; j++) { char letter = word.charAt(j); counts[letter - 'a']++; if (counts[letter - 'a'] > available[letter - 'a']) return false; } } } return true; } public int calculateScore(String[] words, int[] bits, int[] score) { int totalScore = 0; int length = words.length; for (int i = 0; i < length; i++) { if (bits[i] == 1) { String word = words[i]; int wordLength = word.length(); for (int j = 0; j < wordLength; j++) { char letter = word.charAt(j); totalScore += score[letter - 'a']; } } } return totalScore; } }
-
// OJ: https://leetcode.com/problems/maximum-score-words-formed-by-letters/ // Time: O(2^N * C) // Space: O(2^N * C) class Solution { public: int maxScoreWords(vector<string>& A, vector<char>& letters, vector<int>& score) { int avail[26] = {}, ans = 0, cnt[14][26] = {}, wordScore[14] = {}, N = A.size(); vector<array<int, 26>> used(1 << N); vector<int> scoreSum(1 << N); for (char c : letters) avail[c - 'a']++; for (int i = 0; i < N; ++i) { for (char c : A[i]) { cnt[i][c - 'a']++; wordScore[i] += score[c - 'a']; } } for (int m = 1; m < 1 << N; ++m) { int lb = m & -m, i = __builtin_ctz(lb); used[m] = used[m - lb]; for (int j = 0; j < 26; ++j) used[m][j] += cnt[i][j]; int j = 0; for (; j < 26 && used[m][j] <= avail[j]; ++j); if (j < 26) continue; scoreSum[m] = scoreSum[m - lb] + wordScore[i]; ans = max(ans, scoreSum[m]); } return ans; } };
-
class Solution: def maxScoreWords( self, words: List[str], letters: List[str], score: List[int] ) -> int: cnt = Counter(letters) n = len(words) ans = 0 for i in range(1 << n): cur = Counter(''.join([words[j] for j in range(n) if i >> j & 1])) if all(v <= cnt[c] for c, v in cur.items()): t = sum(v * score[ord(c) - ord('a')] for c, v in cur.items()) ans = max(ans, t) return ans
-
func maxScoreWords(words []string, letters []byte, score []int) (ans int) { cnt := [26]int{} for _, c := range letters { cnt[c-'a']++ } n := len(words) for i := 0; i < 1<<n; i++ { cur := [26]int{} for j := 0; j < n; j++ { if i>>j&1 == 1 { for _, c := range words[j] { cur[c-'a']++ } } } ok := true t := 0 for i, v := range cur { if v > cnt[i] { ok = false break } t += v * score[i] } if ok && ans < t { ans = t } } return }