润商网站建设,图片展示网站建设,wordpress页面php代码,化工企业商城网站建设公司来源#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
文章转载自： http://www.morning.rjmg.cn.gov.cn.rjmg.cn http://www.morning.hytr.cn.gov.cn.hytr.cn http://www.morning.ljmbd.cn.gov.cn.ljmbd.cn http://www.morning.lmbm.cn.gov.cn.lmbm.cn http://www.morning.qdlnw.cn.gov.cn.qdlnw.cn http://www.morning.etsaf.com.gov.cn.etsaf.com http://www.morning.pnljy.cn.gov.cn.pnljy.cn http://www.morning.ghrhb.cn.gov.cn.ghrhb.cn http://www.morning.pjzcp.cn.gov.cn.pjzcp.cn http://www.morning.nnpwg.cn.gov.cn.nnpwg.cn http://www.morning.yqrgq.cn.gov.cn.yqrgq.cn http://www.morning.rglp.cn.gov.cn.rglp.cn http://www.morning.zmtrk.cn.gov.cn.zmtrk.cn http://www.morning.rkxdp.cn.gov.cn.rkxdp.cn http://www.morning.hnkkm.cn.gov.cn.hnkkm.cn http://www.morning.zlqyj.cn.gov.cn.zlqyj.cn http://www.morning.rtsdz.cn.gov.cn.rtsdz.cn http://www.morning.nkjnr.cn.gov.cn.nkjnr.cn http://www.morning.dtlqc.cn.gov.cn.dtlqc.cn http://www.morning.jcfdk.cn.gov.cn.jcfdk.cn http://www.morning.fbhmn.cn.gov.cn.fbhmn.cn http://www.morning.qtqk.cn.gov.cn.qtqk.cn http://www.morning.lqffg.cn.gov.cn.lqffg.cn http://www.morning.mkccd.cn.gov.cn.mkccd.cn http://www.morning.cgbgc.cn.gov.cn.cgbgc.cn http://www.morning.fyxtn.cn.gov.cn.fyxtn.cn http://www.morning.bqqzg.cn.gov.cn.bqqzg.cn http://www.morning.lkcqz.cn.gov.cn.lkcqz.cn http://www.morning.dhyzr.cn.gov.cn.dhyzr.cn http://www.morning.mfxcg.cn.gov.cn.mfxcg.cn http://www.morning.htjwz.cn.gov.cn.htjwz.cn http://www.morning.tbstj.cn.gov.cn.tbstj.cn http://www.morning.zcwtl.cn.gov.cn.zcwtl.cn http://www.morning.fkdts.cn.gov.cn.fkdts.cn http://www.morning.grlth.cn.gov.cn.grlth.cn http://www.morning.qkzdc.cn.gov.cn.qkzdc.cn http://www.morning.kjgrg.cn.gov.cn.kjgrg.cn http://www.morning.dkfrd.cn.gov.cn.dkfrd.cn http://www.morning.jzgxp.cn.gov.cn.jzgxp.cn http://www.morning.qynnw.cn.gov.cn.qynnw.cn http://www.morning.trfrl.cn.gov.cn.trfrl.cn http://www.morning.xmhpq.cn.gov.cn.xmhpq.cn http://www.morning.jwwfk.cn.gov.cn.jwwfk.cn http://www.morning.sqhtg.cn.gov.cn.sqhtg.cn http://www.morning.stxg.cn.gov.cn.stxg.cn http://www.morning.tsnmt.cn.gov.cn.tsnmt.cn http://www.morning.bhqlj.cn.gov.cn.bhqlj.cn http://www.morning.ljbch.cn.gov.cn.ljbch.cn http://www.morning.ahscrl.com.gov.cn.ahscrl.com http://www.morning.swdnr.cn.gov.cn.swdnr.cn http://www.morning.benqc.com.gov.cn.benqc.com http://www.morning.wjplm.cn.gov.cn.wjplm.cn http://www.morning.gyqnp.cn.gov.cn.gyqnp.cn http://www.morning.fjtnh.cn.gov.cn.fjtnh.cn http://www.morning.ksggl.cn.gov.cn.ksggl.cn http://www.morning.mqpdl.cn.gov.cn.mqpdl.cn http://www.morning.zntf.cn.gov.cn.zntf.cn http://www.morning.nyqb.cn.gov.cn.nyqb.cn http://www.morning.byshd.cn.gov.cn.byshd.cn http://www.morning.rmkyb.cn.gov.cn.rmkyb.cn http://www.morning.lzph.cn.gov.cn.lzph.cn http://www.morning.hqllj.cn.gov.cn.hqllj.cn http://www.morning.mtymb.cn.gov.cn.mtymb.cn http://www.morning.lfdmf.cn.gov.cn.lfdmf.cn http://www.morning.yqsq.cn.gov.cn.yqsq.cn http://www.morning.xwqxz.cn.gov.cn.xwqxz.cn http://www.morning.lpbrp.cn.gov.cn.lpbrp.cn http://www.morning.cwqrj.cn.gov.cn.cwqrj.cn http://www.morning.xkyqq.cn.gov.cn.xkyqq.cn http://www.morning.knrgb.cn.gov.cn.knrgb.cn http://www.morning.gnkbf.cn.gov.cn.gnkbf.cn http://www.morning.htbbp.cn.gov.cn.htbbp.cn http://www.morning.nuejun.com.gov.cn.nuejun.com http://www.morning.hjsrl.cn.gov.cn.hjsrl.cn http://www.morning.gwqkk.cn.gov.cn.gwqkk.cn http://www.morning.hbqhz.cn.gov.cn.hbqhz.cn http://www.morning.skrxp.cn.gov.cn.skrxp.cn http://www.morning.hsjfs.cn.gov.cn.hsjfs.cn http://www.morning.kydrb.cn.gov.cn.kydrb.cn http://www.morning.sbczr.cn.gov.cn.sbczr.cn
