用枚举算法解决Leetcode第318题最大单词长度乘积问题

news/2024/7/25 21:44:42/文章来源:https://blog.csdn.net/2302_79682652/article/details/139267499

318. 最大单词长度乘积

难度:中等

问题描述:

给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母。如果不存在这样的两个单词,返回 0 。

示例 1:

输入:words = ["abcw","baz","foo","bar","xtfn","abcdef"]

输出:16

解释:这两个单词为 "abcw", "xtfn"。

示例 2:

输入:words = ["a","ab","abc","d","cd","bcd","abcd"]

输出:4

解释:这两个单词为 "ab", "cd"。

示例 3:

输入:words = ["a","aa","aaa","aaaa"]

输出:0

解释:不存在这样的两个单词。

提示:

2 <= words.length <= 1000

1 <= words[i].length <= 1000

words[i] 仅包含小写字母

这个问题可以借助枚举算法来解决

枚举算法的基本思想是列举出问题所有可能的解,然后检验每一个列举是否为问题真正的解。它涉及到三个重要步骤:确定研究范围、列举和检验。

具体到本题中

研究范围:words数组中所有的单词构成的两两组合

列举:利用二重循环遍历出words中不同的单词组合

检验:对取出的两个单词判断是否有公共字符,如果没有,再检验字符长度的乘积是否最大

实现依据:

1、求两个单词长度的乘积,如果两个单词分别为word1和word2,则长度的乘积k=len(word1)*len(word2)

2、如何判断两个单词没有公共字母?对于两个单词word1和word2,先将其转换为集合分别去掉重复字符,然后观察集合的长度之和与它们并集的长度是否相等,如果相等,说明没有公共字符,否则有。 

 程序如下:

#检查是否有公共字符,如果有返回True,否则返回False
def checkshare(word1,word2):word1=set(word1)word2=set(word2)word=word1|word2if len(word)==len(word1)+len(word2):return Falseelse:return True#利用二重循环枚举,返回满足条件的最大单词长度乘积
def maxproduct(words):n=len(words)maxlen=0for i in range(n-1):for j in range(i+1,n):k=len(words[i])*len(words[j])if (not checkshare(words[i],words[j])) and k>maxlen:maxlen=kreturn maxlen#输入
words=eval(input('pls input words='))#输出
print(maxproduct(words))

运行实例一

pls input words=['abc','def','cdefgh','ijklmn']

36

运行实例二

pls input words=['ab','ac','cd','defgh']

10

感悟:长城不是一天修成的,不必太在意题的难易,只要脚踏实地,认认真真解决好每一道题,必然有所收获。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1053715.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

conda 环境找不到 libnsl.so.1

安装prokka后运行报错 perl: error while loading shared libraries: libnsl.so.1: cannot open shared object file: No such file or directory 通过conda list 可以看到 有libsnl 2.00版本&#xff0c;通过修改软链接方式进行欺骗

面试题:字符串“1024“不强转怎么变成数字1024(ASCII应用)

面试题&#xff1a;就是面试官很秀的场合。怎么把字符串"1024"转成1024 1.ASCII码表是什么&#xff1f; ASCII(American Standard Code for Information Interchange)码表使用用于将字符转换成对应数字的编码规范。它由美国国家标准协会(ANSI)于1963年制定&#xf…

Llama模型家族训练奖励模型Reward Model技术及代码实战(二)从用户反馈构建比较数据集

LlaMA 3 系列博客 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;一&#xff09; 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;二&#xff09; 基于 LlaMA 3 LangGraph 在windows本地部署大模型 &#xff08;三&#xff09; 基于 LlaMA…

AAAI2024 基于扩散模型 多类别 工业异常检测 DiAD

前言 本文分享一个基于扩散模型的多类别异常检测框架&#xff0c;用于检测工业场景的缺陷检测或异常检测。 设计SG语义引导网络&#xff0c;在重建过程中有效保持输入图像的语义信息&#xff0c;解决了LDM在多类别异常检测中的语义信息丢失问题。高效重建&#xff0c;通过在潜…

rust语言初识

程序设计实践课上水一篇ing 来源&#xff1a;rust基础入门-1.初识rust-酷程网 (kucoding.com) rust作为一名新兴语言&#xff0c;与go又有些许不同&#xff0c;因为它的目标是对标系统级开发&#xff0c;也就是C、C这两位在编程界的位置。比如我们最常用的windows系统&#x…

【漏洞复现】用友NC registerServlet JNDI 远程代码执行漏洞(XVE-2024-10248)

0x01 产品简介 用友NC是 用友软件股份有限公司开发的一套企业级管理软件系统。它是一个基于互联网的多层应用系统&#xff0c;旨在为中大型企业提供全面、集成的管理解决方案。是一种商业级的企业资源规划云平台&#xff0c;为企业提供全面的管理解决方案&#xff0c;包括财务…

2024年蓝桥杯Web开发【大赛大纲】15届

一、 组别 Web应用开发分为&#xff1a;大学组和职业院校组。 每位选手只能申请参加其中一个组别的竞赛。各个组别单独评奖。 研究生和本科生只能报大学组。 其它高职高专院校可自行选择报任意组别。 二. 竞赛赛程 省赛时长&#xff1a;4小时。 决赛时长&#xff1a;4小…

springcloud-服务拆分与远程调用

一 微服务 1.1简单了解 SpringCloud SpringCloud是目前国内使用最广泛的微服务框架。官网地址&#xff1a;Spring Cloud。 SpringCloud集成了各种微服务功能组件&#xff0c;并基于SpringBoot实现了这些组件的自动装配&#xff0c;从而提供了良好的开箱即用体验&#xff1a…

FME学习之旅---day28

我们付出一些成本&#xff0c;时间的或者其他&#xff0c;最终总能收获一些什么。 教程&#xff1a;CSV 入门 逗号分隔值 &#xff08;CSV&#xff09; 是一种以 ASCII 文件格式存储结构化信息的方法&#xff0c;从而使其成为一个非常简单的数据库。这使其成为电子表格、数据…

Aws CodeCommit代码仓储库

1 创建IAM用户 IAM创建admin用户&#xff0c;增加AWSCodeCommitFullAccess权限 2 创建存储库 CodePipeline -> CodeCommit -> 存储库 创建存储库 3 SSH 1) window环境 3.1.1 上载SSH公有秘钥 生成SSH秘钥ID 3.1.2 编辑本地 ~/.ssh 目录中名为“config”的 SSH 配置文…

Java | Leetcode Java题解之第104题二叉树的最大深度

题目&#xff1a; 题解&#xff1a; class Solution {public int maxDepth(TreeNode root) {if (root null) {return 0;}Queue<TreeNode> queue new LinkedList<TreeNode>();queue.offer(root);int ans 0;while (!queue.isEmpty()) {int size queue.size();wh…

[xx点评完结]——白马点评完整代码+rabbitmq实现异步下单+资料,免费

项目所有功能已测&#xff0c;均可以跑通&#xff0c;Jmeter和RabbitMQ也都测了。 项目源码:dianpinghui: 仿黑马点评项目 资料: https://pan.baidu.com/s/1kTCn9PxgeIey90WgM4KRqA?pwdn66b 对佬有帮助可以给个star哈&#xff0c;感谢&#x1f339;&#x1f339;&#x1f3…

rk3568_semaphore

文章目录 前言1 什么是信号量1.1 信号量API函数2、信号量实验2.1 实验目的2.2函数源码2.3 运行结果图前言 本文记录rk3568开发板的信号量实验 1 什么是信号量 信号量是同步的一种方式,常常用于控制对共享资源的访问。 举个例子:停车场的停车位有100个,这100个停车位就是共…

了解区块链基础设施,共同构建安全且强大的Sui网络

区块链基础设施的范畴很广&#xff0c;但其核心是那些直接与网络互动的计算机。这些实体通常被称为节点&#xff0c;分为不同的类型&#xff0c;例如维护完整区块链副本的全节点&#xff0c;以及作为共识决定者的验证节点。除了这两种类型之外&#xff0c;还有其他类型的节点&a…

DataGear 制作服务端分页的数据可视化看板

DataGear 2.3.0 版本新增了附件图表数据集特性&#xff08;在新建图表时将关联的数据集设置为 附件 &#xff0c;具体参考官网文档定义图表章节&#xff09;&#xff0c;在制作看板时&#xff0c;可以基于此特性&#xff0c;结合dg-chart-listener&#xff0c;利用服务端数据扩…

服务器数据恢复—RAID5阵列崩溃如何恢复上层OA和oracle数据库的数据?

服务器数据恢复环境&故障&#xff1a; 某公司的一台服务器中的raid5磁盘阵列有两块磁盘先后掉线&#xff0c;服务器崩溃。故障服务器的操作系统为linux&#xff0c;操作系统部署了oa&#xff0c;数据库为oracle。oracle数据库已经不再对该oa系统提供后续支持&#xff0c;用…

LabVIEW高低温试验箱控制系统

要实现LabVIEW高低温试验箱控制系统&#xff0c;需要进行硬件配置、软件设计和系统集成&#xff0c;确保LabVIEW能够有效地监控和控制试验箱的温度。以下是详细说明&#xff1a; 硬件配置 选择合适的试验箱&#xff1a; 确定高低温试验箱的型号和品牌。 确认试验箱是否支持外…

springboot项目部署到linux服务器

springboot后端 修改前 修改后 vue前端 修改前 将地址中的 localhost改为 ip 重新生成war包 war上传到linux的tomcat的webapps下 其他环境配置和macOS大差不差 Tomcat安装使用与部署Web项目的三种方法_tomcat部署web项目-CSDN博客

【C++】list的使用方法和模拟实现

❤️欢迎来到我的博客❤️ 前言 list是可以在常数范围内在任意位置进行插入和删除的序列式容器&#xff0c;并且该容器可以前后双向迭代list的底层是双向链表结构&#xff0c;双向链表中每个元素存储在互不相关的独立节点中&#xff0c;在节点中通过指针指向其前一个元素和后…

告别裸奔,聊聊主流消息队列的认证和鉴权!

大家好&#xff0c;我是君哥。 我们在使用消息队列时&#xff0c;经常关注的是消息队列收发消息的功能。但好多时候需要对客户端有一定的限制&#xff0c;比如只有持有令牌的客户端才能访问集权&#xff0c;不允许 Producer 发送消息到某一个 Topic&#xff0c;或者某一个 Top…