【1255. 得分最高的单词集合】
来源:力扣(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
解释:
字母得分为 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] 只包含小写的英文字母。
方法:状态压缩
因为单词数目不超过 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(vector<string>& words, vector<char>& letters, vector<int>& score) {int n = words.size(), res = 0;vector<int> count(26);for (auto c : letters) {count[c - 'a']++;}for (int s = 1; s < (1 << n); s++) {vector<int> 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(∑) 的空间。
author:LeetCode-Solution
相关文章:
【1255. 得分最高的单词集合】
来源:力扣(LeetCode) 描述: 你将会得到一份单词表 words,一个字母表 letters (可能会有重复字母),以及每个字母对应的得分情况表 score。 请你帮忙计算玩家在单词拼写游戏中所能获…...
nginx模块介绍
新编译前,在对应的nginx原编译文件夹 如:nginx-1.23.0 下,要 make clean 清空以前编译的objs文件夹,实际上就是执行了rm objs文件夹。 很多要用到git,先yum install git -y echo-nginx-module 让nginx直接使用echo的…...
排错工具ping和trace(电子科技大学TCP/IP实验四)
一.实验目的 1、了解网络连通性测试的方法和工作原理 2、了解网络路径跟踪的方法和工作原理 3、掌握 MTU 的概念和 IP 分片操作 4、掌握 IP 分组生存时间(TTL)的含义和作用 5、掌握路由表的作用和路由查找算法 二.预备知识 …...
node.js中ws模块创建服务端和客户端
一、WebSocket出现的原因 1、Http协议发布REST API 的不足: 每次请求响应完成之后,服务器与客户端之间的连接就断开了,如果客户端想要继续获取服务器的消息,必须再次向服务器发起请 求。这显然无法适应对实时通信有高要求的场景…...
kubernates-1.26.1 kubeadm containerd 单机部署
k8s1.26 kubeadm containerd 安装 kubeadm init 时提示 containerd 错误 failed to pull image “k8s.gcr.io/pause:3.6” 报错日志显示containerd pull时找不到对应的pause版本,而不是registry.k8s.io/pause:3.9 [rootk8s-master containerd]# kubeadm init --k…...
如何在 iPhone 上恢复已删除的通话记录/通话记录
您的通话记录/通话记录可能很重要,尤其是当您想要拨打之前联系过但未保存的号码时。如果您碰巧删除了通话记录(有意或无意),本指南将帮助您了解如何检索它们并找回您需要使用的所有记录。我们将根据您的情况和您拥有的工具讨论不同…...
Canonical为所有支持的Ubuntu LTS系统发布了新的Linux内核更新
导读Canonical近日为所有支持的Ubuntu LTS系统发布了新的Linux内核更新,以解决总共19个安全漏洞。新的Ubuntu内核更新仅适用于长期支持的Ubuntu系统,包括Ubuntu 22.04 LTS(Jammy Jellyfish)、Ubuntu 20.04 LTS(Focal F…...
MS9122是一款USB单芯片投屏器,内部集成了USB2 0 控制器和数据收发模块、HDMI 数据接口和音视频处理模块。MS9122可以通过USB接口显示
MS9122是一款USB单芯片投屏器,内部集成了USB2.0 控制器和数据收发模块、HDMI 数据接口和音视频处理模块。MS9122可以通过USB接口显示或者扩展PC、智能手机、平板电脑的显示信息到更大尺寸的显示设备,支持HDMI视频接口。 主要功能特征 HDMI v1.4兼容 最大…...
C++学习笔记-数据抽象
简单的说,数据抽象是用来描述数据结构的。数据抽象就是 ADT。一个 ADT 主要表现为它支持的一些操作,比方说 stack.push、stack.pop,这些操作应该具有明确的时间和空间复杂度。另外,一个 ADT 可以隐藏其实现细节,比方说…...
【Android】Android开发笔记(一)
【Android】Android开发笔记(一) 在Android Studio中import module和delete moduleimport moduledelete moduleAndroid Studio中App(Module)无法正常运行在实机上测试App一些基本概念App的工程结构结语在Android Studio中import m…...
C语言数据结构(二)—— 受限线性表 【栈(Stack)、队列(Queue)】
在数据结构逻辑层次上细分,线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”,可以自由的删除或添加结点。受限线性表主要包括栈和队列,受限表示对结点的操作受限制。一般线性表详解,请参考文章&…...
线程安全之synchronized和volatile
目录 1.线程不安全的原因 2.synchronized和volatile 2.1 synchronized 2.1.1 synchornized的特性 2.1.2 synchronized使用示例 2.2 volatile 我们先来看一段代码: 分析以上代码,t1和t2这两个线程的任务都是分别将count这个变量自增5000次ÿ…...
量子计算对网络安全的影响
量子计算的快速发展,例如 IBM 的 Quantum Condor 处理器具有 1000 个量子比特的容量,促使专家们宣称第四次工业革命即将实现“量子飞跃”。 量子计算机的指数处理能力已经受到政府和企业的欢迎。 由于从学术和物理原理到商业可用解决方案的不断转变&am…...
MyBatis——增删改查操作的实现
开启mybatis sql日志打印 可以在日志中看到sql中执行的语句 在配置文件中加上下面这几条语句 mybatis.configuration.log-implorg.apache.ibatis.logging.stdout.StdOutImpl logging.level.com.example.demodebug查询操作 根据用户id查询用户 UserMapper: User…...
【7】linux命令每日分享——cat查看文件内容
大家好,这里是sdust-vrlab,Linux是一种免费使用和自由传播的类UNIX操作系统,Linux的基本思想有两点:一切都是文件;每个文件都有确定的用途;linux涉及到IT行业的方方面面,在我们日常的学习中&…...
新氧2023年财务业绩预测:退市风险大幅降低,收入增长将放缓
来源:猛兽财经 作者:猛兽财经 公司进展 与新氧(SY)有关的两个重要积极进展值得一提。 第一个积极进展是新氧的退市风险已在很大程度上降低。 2023年1月6日,新氧披露,它已经“重新符合纳斯达克规定的股价每…...
C++使用shared_ptr与weak_ptr轻松管理内存
智能指针之shared_ptr与weak_ptr前言智能指针实例分析前言 C与其他语言的不同点之一就是可以直接操作内存,这是一把双刃剑,直接操作内存可以提高开发的灵活度,开发人员在合适的时机申请内存,在合适的时机释放内存,减少…...
Buuctf reverse [FlareOn4]IgniteMe 题解
一. 查壳 无壳32位程序 二. ida打开 GetStdHandle函数根据微软官方文档可以得知是获取标准输入/输出/错误的句柄 参数里的 0xFFFFFFF6转换一下是4294967286, 对应(DWORD) -10 所以这里的WriteFile函数实际上是实现了printf的功能 sub_4010F0()函数 其功能是通过ReadFile函数读取…...
ChatGPT懂SAP吗?跟ChatGPT聊完后,我暂时不担心会失业
我弄了个ChatGPT账号。随便问了一下他SAP的问题。贴出来跟大家分享一下。 问题1:我是 SAP 开发工程师,你有什么可以帮到我。 作为一个语言模型,我可以为您提供关于SAP开发的一般性建议,以及关于如何使用SAP软件的一些技巧。以下是…...
Communications link failure 解决方法 !!!
Communications link failure 解决方法 最近在使用mybatis逆向生成的时候遇到了link failure的问题, 这里记录解决方法 文章目录Communications link failure 解决方法generatorConfig 里的数据库链接或数据库或密码或账户填写错误mysql响应时间设置太短, 还没等链接上就关闭连…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?
Redis 的发布订阅(Pub/Sub)模式与专业的 MQ(Message Queue)如 Kafka、RabbitMQ 进行比较,核心的权衡点在于:简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...
