1255. 得分最高的单词集合 (Hard)
2024-10-21 03:38:33
问题描述
你将会得到一份单词表 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]
只包含小写的英文字母。
解题思路
利用哈希表letters_arr
记录回溯过程中的剩余的字母可用次数变化,回溯即可。
代码
class Solution {
public:
int dfs(int st_idx, vector<int> &letters_arr, vector<string> &words, vector<int> &score) {
if (st_idx >= words.size()) {
return 0;
}
int maxnum = 0;
for (int i = st_idx; i < words.size(); i++) {
int total = 0;
bool check = true;
for (char &c : words[i]) {
letters_arr[c - 'a']--;
total += score[c - 'a'];
if (letters_arr[c - 'a'] < 0) {
check = false;
}
}
if (check) {
maxnum = std::max(maxnum, total + dfs(i + 1, letters_arr, words, score));
}
for (char &c : words[i]) {
letters_arr[c - 'a']++;
}
}
return maxnum;
}
int maxScoreWords(vector<string> &words, vector<char> &letters, vector<int> &score) {
vector<int> words_arr(26, 0);
vector<int> letters_arr(26, 0);
for (int i = 0; i < letters.size(); i++) {
letters_arr[letters[i] - 'a']++;
}
// 回溯
return dfs(0, letters_arr, words, score);
}
};
最新文章
- Vagrant 基础全面解析
- jQuery的DOM操作实例(3)——创建节点&;&;编写一个弹窗
- HTTPS学习总结
- C# ADO.NET SqlDataAdapter中传递参数
- Python连接MySQL数据库
- windows cmd color setup
- AutoHotKey 脚本集中营(一)
- js 不可变的原始值和可变的对象引用
- BZOJ3439: Kpm的MC密码
- nginx 一般配置实例 静态页面
- iOS开发之MD5封装及应用
- transition与visibility与display
- Ajax常用实例
- 史上最全的JFinal源码分析(不间断更新)
- 关于DOM的事件操作
- Oracle Client(客户端) 安装与配置
- Chrome默认搜索引擎被窜改
- Linux-vim文本编辑器
- 在python中使用正则表达式(三)
- 完全卸载vs2013 2015
热门文章
- 使用clipboard.js复制文字+图片到微信后图片不显示问题处理
- Kubernetes 设置master相关
- 解决Vue刷新后页面数据丢失的问题(sessionStorage和localStorage的用法)
- ubuntu下安装使用jupyter
- 078_Sublime HaoIDE 搭建 Lightning Aura环境
- crontal 计划任务
- c# message (转)
- GPS授时仪(网络校时服务器)成功投运攀枝花市中西医结合医院
- 03java基础(二)java面向对象
- HCIP-ICT实战进阶08-以太网链路的聚合和集群