当前位置: 首页 > news >正文

【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. 得分最高的单词集合】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 你将会得到一份单词表 words&#xff0c;一个字母表 letters &#xff08;可能会有重复字母&#xff09;&#xff0c;以及每个字母对应的得分情况表 score。 请你帮忙计算玩家在单词拼写游戏中所能获…...

nginx模块介绍

新编译前&#xff0c;在对应的nginx原编译文件夹 如&#xff1a;nginx-1.23.0 下&#xff0c;要 make clean 清空以前编译的objs文件夹&#xff0c;实际上就是执行了rm objs文件夹。 很多要用到git&#xff0c;先yum install git -y echo-nginx-module 让nginx直接使用echo的…...

排错工具ping和trace(电子科技大学TCP/IP实验四)

一&#xff0e;实验目的 1、了解网络连通性测试的方法和工作原理 2、了解网络路径跟踪的方法和工作原理 3、掌握 MTU 的概念和 IP 分片操作 4、掌握 IP 分组生存时间&#xff08;TTL&#xff09;的含义和作用 5、掌握路由表的作用和路由查找算法 二&#xff0e;预备知识 …...

node.js中ws模块创建服务端和客户端

一、WebSocket出现的原因 1、Http协议发布REST API 的不足&#xff1a; 每次请求响应完成之后&#xff0c;服务器与客户端之间的连接就断开了&#xff0c;如果客户端想要继续获取服务器的消息&#xff0c;必须再次向服务器发起请 求。这显然无法适应对实时通信有高要求的场景…...

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版本&#xff0c;而不是registry.k8s.io/pause:3.9 [rootk8s-master containerd]# kubeadm init --k…...

如何在 iPhone 上恢复已删除的通话记录/通话记录

您的通话记录/通话记录可能很重要&#xff0c;尤其是当您想要拨打之前联系过但未保存的号码时。如果您碰巧删除了通话记录&#xff08;有意或无意&#xff09;&#xff0c;本指南将帮助您了解如何检索它们并找回您需要使用的所有记录。我们将根据您的情况和您拥有的工具讨论不同…...

Canonical为所有支持的Ubuntu LTS系统发布了新的Linux内核更新

导读Canonical近日为所有支持的Ubuntu LTS系统发布了新的Linux内核更新&#xff0c;以解决总共19个安全漏洞。新的Ubuntu内核更新仅适用于长期支持的Ubuntu系统&#xff0c;包括Ubuntu 22.04 LTS&#xff08;Jammy Jellyfish&#xff09;、Ubuntu 20.04 LTS&#xff08;Focal F…...

MS9122是一款USB单芯片投屏器,内部集成了USB2 0 控制器和数据收发模块、HDMI 数据接口和音视频处理模块。MS9122可以通过USB接口显示

MS9122是一款USB单芯片投屏器&#xff0c;内部集成了USB2.0 控制器和数据收发模块、HDMI 数据接口和音视频处理模块。MS9122可以通过USB接口显示或者扩展PC、智能手机、平板电脑的显示信息到更大尺寸的显示设备&#xff0c;支持HDMI视频接口。 主要功能特征 HDMI v1.4兼容 最大…...

C++学习笔记-数据抽象

简单的说&#xff0c;数据抽象是用来描述数据结构的。数据抽象就是 ADT。一个 ADT 主要表现为它支持的一些操作&#xff0c;比方说 stack.push、stack.pop&#xff0c;这些操作应该具有明确的时间和空间复杂度。另外&#xff0c;一个 ADT 可以隐藏其实现细节&#xff0c;比方说…...

【Android】Android开发笔记(一)

【Android】Android开发笔记&#xff08;一&#xff09; 在Android Studio中import module和delete moduleimport moduledelete moduleAndroid Studio中App&#xff08;Module&#xff09;无法正常运行在实机上测试App一些基本概念App的工程结构结语在Android Studio中import m…...

C语言数据结构(二)—— 受限线性表 【栈(Stack)、队列(Queue)】

在数据结构逻辑层次上细分&#xff0c;线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”&#xff0c;可以自由的删除或添加结点。受限线性表主要包括栈和队列&#xff0c;受限表示对结点的操作受限制。一般线性表详解&#xff0c;请参考文章&…...

线程安全之synchronized和volatile

目录 1.线程不安全的原因 2.synchronized和volatile 2.1 synchronized 2.1.1 synchornized的特性 2.1.2 synchronized使用示例 2.2 volatile 我们先来看一段代码&#xff1a; 分析以上代码&#xff0c;t1和t2这两个线程的任务都是分别将count这个变量自增5000次&#xff…...

量子计算对网络安全的影响

量子计算的快速发展&#xff0c;例如 IBM 的 Quantum Condor 处理器具有 1000 个量子比特的容量&#xff0c;促使专家们宣称第四次工业革命即将实现“量子飞跃”。 量子计算机的指数处理能力已经受到政府和企业的欢迎。 由于从学术和物理原理到商业可用解决方案的不断转变&am…...

MyBatis——增删改查操作的实现

开启mybatis sql日志打印 可以在日志中看到sql中执行的语句 在配置文件中加上下面这几条语句 mybatis.configuration.log-implorg.apache.ibatis.logging.stdout.StdOutImpl logging.level.com.example.demodebug查询操作 根据用户id查询用户 UserMapper&#xff1a; User…...

【7】linux命令每日分享——cat查看文件内容

大家好&#xff0c;这里是sdust-vrlab&#xff0c;Linux是一种免费使用和自由传播的类UNIX操作系统&#xff0c;Linux的基本思想有两点&#xff1a;一切都是文件&#xff1b;每个文件都有确定的用途&#xff1b;linux涉及到IT行业的方方面面&#xff0c;在我们日常的学习中&…...

新氧2023年财务业绩预测:退市风险大幅降低,收入增长将放缓

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 公司进展 与新氧&#xff08;SY&#xff09;有关的两个重要积极进展值得一提。 第一个积极进展是新氧的退市风险已在很大程度上降低。 2023年1月6日&#xff0c;新氧披露&#xff0c;它已经“重新符合纳斯达克规定的股价每…...

C++使用shared_ptr与weak_ptr轻松管理内存

智能指针之shared_ptr与weak_ptr前言智能指针实例分析前言 C与其他语言的不同点之一就是可以直接操作内存&#xff0c;这是一把双刃剑&#xff0c;直接操作内存可以提高开发的灵活度&#xff0c;开发人员在合适的时机申请内存&#xff0c;在合适的时机释放内存&#xff0c;减少…...

Buuctf reverse [FlareOn4]IgniteMe 题解

一. 查壳 无壳32位程序 二. ida打开 GetStdHandle函数根据微软官方文档可以得知是获取标准输入/输出/错误的句柄 参数里的 0xFFFFFFF6转换一下是4294967286, 对应(DWORD) -10 所以这里的WriteFile函数实际上是实现了printf的功能 sub_4010F0()函数 其功能是通过ReadFile函数读取…...

ChatGPT懂SAP吗?跟ChatGPT聊完后,我暂时不担心会失业

我弄了个ChatGPT账号。随便问了一下他SAP的问题。贴出来跟大家分享一下。 问题1&#xff1a;我是 SAP 开发工程师&#xff0c;你有什么可以帮到我。 作为一个语言模型&#xff0c;我可以为您提供关于SAP开发的一般性建议&#xff0c;以及关于如何使用SAP软件的一些技巧。以下是…...

Communications link failure 解决方法 !!!

Communications link failure 解决方法 最近在使用mybatis逆向生成的时候遇到了link failure的问题, 这里记录解决方法 文章目录Communications link failure 解决方法generatorConfig 里的数据库链接或数据库或密码或账户填写错误mysql响应时间设置太短, 还没等链接上就关闭连…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...