图片展示网站建设,怎么做网站扩展,app首页设计模板,网站信息化建设案例来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
你将会得到一份单词表 words#xff0c;一个字母表 letters #xff08;可能会有重复字母#xff09;#xff0c;以及每个字母对应的得分情况表 score。
请你帮忙计算玩家在单词拼写游戏中所能获…来源力扣LeetCode
描述
你将会得到一份单词表 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
解释
字母得分为 a1, c9, d5, g3, o2
使用给定的字母表 letters我们可以拼写单词 dad (515)和 good (3225)得分为 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
解释
字母得分为 a4, b4, c4, x5, z10
使用给定的字母表 letters我们可以组成单词 ax (45) bx (45) 和 cx (45) 总得分为 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 141 words[i].length 151 letters.length 100letters[i].length 1score.length 260 score[i] 10words[i] 和 letters[i] 只包含小写的英文字母。
方法状态压缩
因为单词数目不超过 14因此我们可以使用状态压缩的方式来枚举所有的单词子集。使用整数 s 表示单词子集s 的第 k 位为 1 代表单词子集 s 包含单词 words[k]s 的第 k 位为 0 代表单词子集 s 不包含单词 words[k]。
使用 count 保存字母表 letters 中各种字母的数目使用 wordCount 保存单词子集 s 中所有单词的各种字母的数目。
枚举所有的单词子集遍历单词子集的单词并更新 wordCount如果 wordCount 中的任一字母的数目都小于等于 count 中对应字母的数目那么说明单词子集的单词可以由字母表 letters 拼写计算单词子集的分数最终结果就是这些分数中的最大值。
代码
class Solution {
public:int maxScoreWords(vectorstring words, vectorchar letters, vectorint score) {int n words.size(), res 0;vectorint count(26);for (auto c : letters) {count[c - a];}for (int s 1; s (1 n); s) {vectorint wordCount(26); // 统计子集 s 所有单词的字母数目for (int k 0; k n; k) {if ((s (1 k)) 0) { // words[k] 不在子集 s 中continue;}for (auto c : words[k]) {wordCount[c - a];}}bool ok true; // 判断子集 s 是否合法int sum 0; // 保存子集 s 的得分for (int i 0; i 26; i) {sum score[i] * wordCount[i];ok ok (wordCount[i] count[i]);}if (ok) {res max(res, sum);}}return res;}
};执行用时40 ms, 在所有 C 提交中击败了32.63%的用户 内存消耗19.6 MB, 在所有 C 提交中击败了40.00%的用户 复杂度分析 时间复杂度O(L(S∑)×2n)其中 L 是数组 letters 的长度S 是字符串数组 words 的所有字符串长度∑ 26 是字符集大小。words 中的每个单词存在于 2n−1 个子集中因此每个单词被遍历 2n−1 次。 空间复杂度O(∑)。保存 count 和 wordCount 需要 O(∑) 的空间。 authorLeetCode-Solution
