LeetCode 1255. 得分最高的单词集合(回溯)
发布日期:2021-07-01 03:27:02
浏览次数:2
分类:技术文章
本文共 2568 字,大约阅读时间需要 8 分钟。
1. 题目
你将会得到一份单词表 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 <= 141 <= words[i].length <= 151 <= letters.length <= 100letters[i].length == 1score.length == 260 <= score[i] <= 10words[i] 和 letters[i] 只包含小写的英文字母。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-score-words-formed-by-letters 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
- 看数据量不是很大,直接回溯,枚举所有可能(每个单词取或者不取,214=16384)
class Solution { int maxscore = 0;public: int maxScoreWords(vector& words, vector & letters, vector & score) { int n = words.size(), i; vector count(26,0); for(i = 0; i < letters.size(); ++i) count[letters[i]-'a']++;//可使用的字母数量 dfs(words, count, score, 0, 0); return maxscore; } void dfs(vector & words, vector & count, vector & score, int i, int sc) { if(i == words.size()) { if(canAdd(count))//所选单词组合满足条件 maxscore = max(maxscore, sc); return; } //加入该单词 for(int j = 0; j < words[i].size(); ++j) { //更新单词得分,计数减少 sc += score[words[i][j]-'a']; count[words[i][j]-'a']--; } dfs(words, count, score, i+1, sc); for(int j = 0; j < words[i].size(); ++j) { //回溯,计数重置,得分减去 sc -= score[words[i][j]-'a']; count[words[i][j]-'a']++; } //不加入该单词 dfs(words, count, score, i+1, sc); } bool canAdd(vector & count) { for(int i = 0; i < 26; ++i) { if(count[i] < 0) return false; } return true; }};
32 ms 8.7 MB
转载地址:https://michael.blog.csdn.net/article/details/106826585 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月21日 18时06分05秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【大数据开发】Java基础 -总结21-Hashmap和HashTable的区别
2019-05-01
Azkaban体系结构
2019-05-01
机器学习之重头戏-特征预处理
2019-05-01
synchronized底层实现及锁的升级、降级
2019-05-01
PermGen space-永久区内存溢出
2019-05-01
Maven继承和聚合
2019-05-01
Apache Kafka:优化部署的 10 种最佳实践
2019-05-01
Leetcode 35. 搜索插入位置 c#
2019-05-01
[9] JMeter-常用函数的使用
2019-05-01
[12] JMeter-结果分析之图形图表
2019-05-01
has been blocked by CORS policy: Response to preflight request doesn‘t pass access control check 报错
2019-05-01
使用aspose.words 18.6实现pdf文档转换
2019-05-01
Java数组详解
2019-05-01
Java面向对象详解
2019-05-01
vs中动态DLL与静态LIB工程中加入版本信息的方法
2019-05-01
大数据分析技术与应用一站式学习(值得收藏)_v20200418
2019-05-01