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

LC-1255. 得分最高的单词集合(回溯)

1255. 得分最高的单词集合

难度困难60

你将会得到一份单词表 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匹配word了

  • 子集型回溯(选还是不选)
class Solution {// 子集型回溯 :枚举word[i]选还是不选String[] words;int[] score, count = new int[26];int res;public int maxScoreWords(String[] words, char[] letters, int[] score) {this.words = words;this.score = score;for(char c : letters) count[c-'a']++;res = 0;dfs(words.length - 1,0);return res;}// 从前i个单词中继续选择,当前得分为totalpublic void dfs(int i, int total){if(i < 0){res = Math.max(res, total);return;} // 不选word[i]dfs(i-1, total);// 选word[i] 先判断合法不合法char[] s = words[i].toCharArray();boolean flag = true;for(char c : s){if(count[c-'a']-- == 0) flag = false;total += score[c-'a'];}if(flag) dfs(i-1, total);for(char c : s){++count[c-'a'];}}
}

相关文章:

LC-1255. 得分最高的单词集合(回溯)

1255. 得分最高的单词集合 难度困难60 你将会得到一份单词表 words&#xff0c;一个字母表 letters &#xff08;可能会有重复字母&#xff09;&#xff0c;以及每个字母对应的得分情况表 score。 请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」&#xff1a;能够由…...

从中国文化看面试挑人标准

文章目录标准一、面相1. 1 四白眼1.2 浓眉二、讲话2.1 言多与气虚总结本文结合中国面相&#xff0c;是个概率性问题&#xff0c;对于个体无效。 标准 正直&#xff0c;三观正&#xff0c;沟通好&#xff0c;技术。从概率上讲&#xff1a; 正直且三观正的人----有恒心&#x…...

谦卑对象设计模式

谦卑设计模式介绍 “谦卑”在这里是拟人化的,指难以测试的对象清晰地认识到自己的局限性,只发挥自己的桥梁和通信作用,并不从中干预信息的传输。 谦卑对象模式‘最初的设计目的是帮助单元测试的编写者区分容易测试的行为与难以测试的行为&#xff0c;并将它们隔离。其设计思路…...

QML Animation动画详解

1.Animation简介 Animation类型提供了四个属性&#xff1a; alwaysRunToEnd&#xff1a;该属性接收布尔类型的参数。该属性保存动画是否运行到完成才停止。当loops属性被设置时&#xff0c;这个属性是最有用的&#xff0c;因为动画将正常播放结束&#xff0c;但不会重新启动。…...

C#开发的OpenRA的加载界面边框的细节

C#开发的OpenRA的加载界面边框的细节 在前面已经看到加载整个界面, 如果仔细地看,会发现加载界面的边框有一个红色的框。 这个红色的边框到底是怎么样来的呢? 其实它不是实时画上去的,而从纹理贴图里贴上去的。 也许有一些人会问,纹理贴图里的图片这么小,怎么样会有这么大…...

计算机网络笔记、面试八股(四)—— TCP连接

本章目录4. TCP连接4.1 TCP报文段的首部格式4.2 TCP连接如何保证可靠4.3 ARQ协议4.3.1 停止等待ARQ协议4.3.1.1 无差错情况4.3.1.2 出现差错情况4.3.1.3 确认丢失和确认迟到4.3.2 连续ARQ协议4.3.2.1 流水线传输4.3.2.2 累积确认4.3.2.3 滑动窗口协议4.3.3 停止等待ARQ和连续AR…...

Centos7 安装jenkins java1.8版本

1. 首先安装好jdk1.8 2. 安装jenkins 命令&#xff1a;(可以在根目录&#xff0c;创建文件夹 mkdir home 然后在此文件夹下操作 cd /home) a 清华源&#xff0c;获取jenkins安装包 wget https://mirrors.tuna.tsinghua.edu.cn/jenkins/redhat/jenkins-2.346-1.1.noarch.rp…...

【每日阅读】JS知识(三)

var声明提升 js是一个解释性语言类型&#xff0c;预解析就是在执行代码之前对代码进行通读 var关键字是&#xff0c;在内存中声明一个变量名 js在代码执行之前 会经历两个环节 解释代码 和执行代码 声明式函数 内存中 先声明一个变量名是函数 这个名代表的是函数 乘法表 // for…...

Vue(6)

文章目录1. 自定义指令1.1 函数式1.2 对象式1.3 自定义指令常见坑1.4 创建全局指令2. 生命周期2.1 引出生命周期2.2 分析生命周期2.3 总结3. 组件3.1 认识组件3.2 使用组件 (非单文件组件)3.3 全局组件3.4 组件的几个注意点3.5 组件的嵌套3.6 VueComponent 构造函数3.7 一个重要…...

Neo4j列表函数

使用列表 标量列表函数 size() 函数返回列表中的元素的数量 MATCH (p:Person)-[:ACTED_IN]->(m:Movie) WITH p, collect (m.title) AS MovieTitles WITH p, MovieTitles, size(MovieTitles) AS NumMovies WHERE NumMovies > 20 RETURN p.name AS Actor, NumMovies, Movie…...

55. 跳跃游戏

给定一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。示例 1&#xff1a;输入&#xff1a;nums [2,3,1,1,4]输出&#xff1a;true解释&#xff1a;可以先跳 1 步&#…...

typedef在c语言中的作用

在 C 语言中&#xff0c;typedef 是一个非常有用的关键字&#xff0c;用于给数据类型定义一个新的名字。typedef 的作用有以下几个方面&#xff1a; 定义新类型名&#xff1a;typedef 可以定义一个新的数据类型名称&#xff0c;使得该类型名称可以在程序中使用。这样可以提高代…...

计算机网络体系结构及分层参考模型

文章目录一、分层设计思想的提出二、网络分层的必要性三、什么是计算机网络体系结构四、计算机网络参考模型OSI参考模型/五层参考模型/TCP/IP参考模型一、分层设计思想的提出 最早提出分层思想的是 ARPANET网。1969年11月&#xff0c;美国国防部开始建立一个命名为ARPANET的网络…...

LLVM程序分析与编译转换框架论文分享

LLVM 2004年论文原文 概述 本文描述了 LLVM&#xff08;低级虚拟机&#xff09;&#xff0c;一种编译器框架&#xff0c;旨在通过在编译时、链接时、运行时&#xff0c;以及运行之间的空闲时间。 LLVM 以静态单一赋值 (SSA) 形式定义了一种通用的低级代码表示&#xff0c;具有…...

《程序员思维修炼》速读笔记

文章目录书籍信息概览绪论从新手到专家的历程认识大脑利用右脑调试大脑主动学习积累经验控制注意力超越专家图解书籍信息 书名&#xff1a;《程序员思维修炼&#xff08;修订版&#xff09;》 作者&#xff1a;[美] Andy Hunt 概览 绪论 再提“实用”关注情境所有人都关注这…...

【Hello Linux】进程概念

作者&#xff1a;小萌新 专栏&#xff1a;Linux 作者简介&#xff1a;大二学生 希望能和大家一起进步&#xff01; 本篇博客简介&#xff1a;简单介绍下进程的概念 进程基本概念PCB 程序控制块task_struct是什么task_struct里面有什么查看进程通过系统目录查看进程通过ps指令查…...

Bunifu.UI.WinForms 6.0.2 Crack

Bunifu.UI.WinForms为 WinForms创建令人惊叹的UI Bunifu.UI.WinForms我们为您提供了现代化的快速用户界面控件。用于 WinForms C# 和 VB.NET 应用程序开发的完美 UI 工具 简单 Bunifu.UI.WinForms没有臃肿的特征。正是您构建令人惊叹的 WinForms 应用程序所需要的。只需拖放然…...

学习 Python 之 Pygame 开发魂斗罗(五)

学习 Python 之 Pygame 开发魂斗罗&#xff08;五&#xff09;继续编写魂斗罗1. 加载地图2. 修改角色尺寸和地面高度继续编写魂斗罗 在上次的博客学习 Python 之 Pygame 开发魂斗罗&#xff08;四&#xff09;中&#xff0c;我们完成了角色的移动和跳跃还有射击&#xff0c;由…...

LeetCode 104. 二叉树的最大深度

LeetCode 104. 二叉树的最大深度 难度&#xff1a;easy\color{Green}{easy}easy 题目描述 给定一个二叉树&#xff0c;找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例&#xff1a; 给定二叉树 [3…...

pandas 中如何按行或列的值对数据排序?

在处理表格型数据时&#xff0c;常会用到排序&#xff0c;比如&#xff0c;按某一行或列的值对表格排序&#xff0c;要怎么做呢&#xff1f; 这就要用到 pandas 中的 sort_values() 函数。 一、 按列的值对数据排序 先来看最常见的情况。 1.按某一列的值对数据排序 以下面…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...