当前位置: 首页 > 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响应时间设置太短, 还没等链接上就关闭连…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...