[LeetCode] 1255. Maximum Score Words Formed by Letters 得分最高的单词集合

2021年11月23日 阅读数:3
这篇文章主要向大家介绍[LeetCode] 1255. Maximum Score Words Formed by Letters 得分最高的单词集合,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Given a list of words, list of  single letters (might be repeating) and score of every character.html

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).java

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.git

Example 1:github

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:code

  • 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 中的单词,每一个字母只能用一次,没必要使用全部的字母,问能够获得的最大分数是多少,每一个拼出的单词的分数是其全部的字母的分数之和。题目中限定了只有小写字母,即 26 个,因此 score 数组的大小也是 26 个,能够直接根据字母取其分数值。对于给定的字母数组 letters,里面可能会存在大量的重复字母,为了便于使用,须要统计每一个字母的个数,能够用一个大小为 26 的 cnt 数组来统计。因为不知道给定的字母能拼出多少个单词,但最终能拼出的单词集必定是给定单词集的子集,须要注意的是也不是拼出的单词越多越好,而是须要最终的得分最大,因此只能尽量的去计算每一种状况,从而找到得分最大的状况。orm

跟以前那道 Subsets 有点相似,不过更加复杂一些。这里使用回溯 Backtracking 的方法来作,递归函数须要4个参数,原单词数组 words,统计字母个数数组 cnts,字母分数数组 score,还有当前遍历的位置 idx。从 idx 的位置开始日后遍历,对于当前遍历到的单词,遍历其每个字母,而且将 cnt 对应的字母个数减1,当小于0了的话,说明此时没法组成当前单词,标记 isValid 为 false,同时将当前单词的总得分存入变量 sum 中。处理完当前单词后,若 isValid 为 true,说明字母是够用的,则对下一个位置的单词调用递归,将返回值加到 sum 中,这样 sum 就是合法的状况,用其来更新结果 res。以后要记得恢复状态,将当前单词的字母统计个数加回来,参见代码以下:htm


解法一:blog

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;
    }
};

咱们还能够写的更简洁一些,在递归函数中少用一个 for 循环,开始直接判断当前 idx 是否大于等于 words 的长度,是的话直接返回0。不然先跳过当单词,直接对下个位置调用递归,获得返回值 skipGain,而后再来计算当前的得分 gain。这里为了不回溯的恢复状态步骤,直接新建了一个字母统计个数数组 cnt1,而后就是遍历当前单词的字母,减小对应字母的个数,若小于0了,isValid 标记为 false,将字母分数加到 gain 中。若最终 isValid 为 true,则分数为 gain 加上对下一个位置调用递归的返回的值(注意此次调用和开头获得的 skipGain 是不一样,由于传入的 cnt 数组不一样,此次调用已经减去当前单词的字母个数),若 isValid 为 false,则分数为0。最终返回的分数还要跟 skipGain 相比,取较大值返回便可,参见代码以下:


解法二:

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);
    }
};

最后来看一种迭代的解法,这里是遍历 words 的全部的子集,用了 bitmask 的方法,若 words 里有n个单词,那么其子集的个数是 2^n,对应的正好是从 0 到 2^n-1 的二进制表示,0位表示不用对应位单词,1表示选用当前单词。好比 words 是 ["a", "b", "c"] 的话,那么 101 就表示子集是 ["a", "c"],这样就能够遍历全部的子集了。开始仍是先统计 letters 中的字母个数,放入到 count 中,而后 mask 从0遍历到 2^n-1,对于每一个子集,复制一个 count 数组,而后遍历n个位置,从0遍历到 n-1,或者从 n-1 遍历到0均可以,为的是找到二进制数对应的1位,经过 (mask >> i) & 1 来判断,遍历须要拼的单词的字母,减去对应的字母个数,若小于0了,标记 isValid,并 break 掉。每遍历完子集中的一个单词,都检查一下 isValid,若为0就 break 掉循环,最终该子集中的单词遍历完了以后,若 isValid 为1,用 sum 来更新结果 res 便可,参见代码以下:


解法三:

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'];
        for (int mask = 0; mask < m; ++mask) {
            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/505887/C%2B%2B-Memory-efficient-simple-bitmasking-solution

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 题目讲解汇总(持续更新中...)