# 1255. Maximum Score Words Formed by Letters

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.

``````class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
vector<int> cnt(26);
for (char c : letters) ++cnt[c - 'a'];
return dfs(words, cnt, score, 0);
}
int dfs(vector<string>& words, vector<int>& cnt, vector<int>& score, int idx) {
int res = 0;
for (int i = idx; i < words.size(); ++i) {
int sum = 0;
bool isValid = true;
for (char c : words[i]) {
if (--cnt[c - 'a'] < 0) {
isValid = false;
}
sum += score[c - 'a'];
}
if (isValid) {
sum += dfs(words, cnt, score, i + 1);
res = max(res, sum);
}
for (char c : words[i]) {
++cnt[c - 'a'];
}
}
return res;
}
};
``````

``````class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
vector<int> cnt(26);
for (char c : letters) ++cnt[c - 'a'];
return dfs(words, cnt, score, 0);
}
int dfs(vector<string>& words, vector<int>& cnt, vector<int>& score, int idx) {
if (idx >= words.size()) return 0;
int skipGain = dfs(words, cnt, score, idx + 1), gain = 0;
bool isValid = true;
vector<int> cnt1 = cnt;
for (char c : words[idx]) {
if (--cnt1[c - 'a'] < 0) isValid = false;
gain += score[c - 'a'];
}
return max(skipGain, isValid ? gain + dfs(words, cnt1, score, idx + 1) : 0);
}
};
``````

``````class Solution {
public:
int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score) {
int res = 0, n = words.size(), m = 1 << n;
vector<int> count(26);
for (char c : letters) ++count[c - 'a'];
int sum = 0, isValid = 1;
vector<int> cnt = count;
for (int i = n - 1; i >= 0; --i) {
if ((mask >> i) & 1) {
for (char c : words[i]) {
if (--cnt[c - 'a'] < 0) {
isValid = 0;
break;
}
sum += score[c - 'a'];
}
}
if (!isValid) break;
}
if (isValid) res = max(res, sum);
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1255

Subsets

https://leetcode.com/problems/maximum-score-words-formed-by-letters/

https://leetcode.com/problems/maximum-score-words-formed-by-letters/discuss/426045/C%2B%2B-DFS-(optional-memo)

https://leetcode.com/problems/maximum-score-words-formed-by-letters/discuss/425129/java-backtrack-similar-to-78.-Subsets-1ms-beats-100

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation