原文链接: https://leetcode-cn.com/problems/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.

中文题目

你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中，分数最高的单词集合的得分。

单词拼写游戏的规则概述如下：

• 玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
• 可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。
• 单词表 words 中每个单词只能计分（使用）一次。
• 根据字母得分情况表score，字母 'a', 'b', 'c', ... , 'z' 对应的得分分别为 score[0], score[1], ..., score[25]。
• 本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。

 

示例 1：

输入：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]
输出：23
解释：
字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters，我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5)，得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。

示例 2：

输入：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]
输出：27
解释：
字母得分为  a=4, b=4, c=4, x=5, z=10
使用给定的字母表 letters，我们可以组成单词 "ax" (4+5)， "bx" (4+5) 和 "cx" (4+5) ，总得分为 27 。
单词 "xxxz" 的得分仅为 25 。

示例 3：

输入：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]
输出：0
解释：
字母 "e" 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。

 

提示：

• 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] 只包含小写的英文字母。

通过代码

高赞题解

解题思路：

1. 提供的字母集合，每个字母只能用一次
2. 提供的单词集合，每个单词也只能用一次
3. 单词集合的大小，1 <= words[i].length <= 15
4. 枚举 words 子集总共 2^15 种情况
5. 对每一种情况统计使用了哪些字母
   1. 如果字母超出范围了，就不符合要求
   2. 否则按照字母表计算得分
   3. 记录最大得分

位压缩：

1. 对于单词集合中每一个词，都可以选择，用/不用

   所以就可以用位 0/1 来表示

2. 单词集合中每个单词都表示出来，总和就是 $2^N$ 种

   可以用 1 << N 来表示

3. 当遍历到其中一个组合时，其数字的二进制位表示的就是各个单词的使用状态

   比如 5，二进制 101，代表第 0 个和第 2 个单词使用，第 1 个单词不使用

4. 检查时，对于第 i 个单词，使用 1 << i，得到二进制除了第 i 位（顺序是从右至左）其余全 0 的数字

   比如第 2 个单词，1 << 2 之后得到 4（二进制 100）

5. 再与状态位进行&操作，得到是否使用

   4（二进制100）与刚才的 5（二进制101）&操作，得到 true

代码：

[-C++]
// 将第（bit）种组合情况，所使用的单词中的字母数量统计出来
vector<int> group(vector<string>& words, int bit)
{
    vector<int> g(26, 0);
    for (int i = 0; i < words.size(); i++)
    {
        if (!(bit & (1 << i))) continue;
        for (auto c : words[i])
        {
            g[c - 'a']++;
        }
    }
    return g;
}

// 根据规则计算得分
int calcScore(vector<int>& group, vector<int>& lettercnt, vector<int>& score)
{
    int s = 0;
    for (int j = 0; j < 26; j++)
    {
        if (lettercnt[j] < group[j]) return 0;
        s += group[j] * score[j];
    }
    return s;
}

int maxScoreWords(vector<string>& words, vector<char>& letters, vector<int>& score)
{
    // 统计给出的字母的数量
    vector<int> lettercnt(26, 0);
    for (auto c : letters)
    {
        lettercnt[c - 'a']++;
    }
    
    int ans = 0;
    for (int i = 0; i < (1 << words.size()); i++)
    {
        auto g = group(words, i);
        ans = max(ans, calcScore(g, lettercnt, score));
    }
    return ans;
}

感谢您的观看，希望对您有帮助，欢迎热烈的交流！

统计信息

通过次数	提交次数	AC比率
3136	4573	68.6%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言