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

【Java|golang】1048. 最长字符串链

给出一个单词数组 words ,其中每个单词都由小写英文字母组成。

如果我们可以 不改变其他字符的顺序 ,在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ,那么我们认为 wordA 是 wordB 的 前身 。

例如,“abc” 是 “abac” 的 前身 ,而 “cba” 不是 “bcad” 的 前身
词链是单词 [word_1, word_2, …, word_k] 组成的序列,k >= 1,其中 word1 是 word2 的前身,word2 是 word3 的前身,依此类推。一个单词通常是 k == 1 的 单词链 。

从给定单词列表 words 中选择单词组成词链,返回 词链的 最长可能长度 。

示例 1:

输入:words = [“a”,“b”,“ba”,“bca”,“bda”,“bdca”]
输出:4
解释:最长单词链之一为 [“a”,“ba”,“bda”,“bdca”]
示例 2:

输入:words = [“xbc”,“pcxbcf”,“xb”,“cxbc”,“pcxbc”]
输出:5
解释:所有的单词都可以放入单词链 [“xb”, “xbc”, “cxbc”, “pcxbc”, “pcxbcf”].
示例 3:

输入:words = [“abcd”,“dbqca”]
输出:1
解释:字链[“abcd”]是最长的字链之一。
[“abcd”,“dbqca”]不是一个有效的单词链,因为字母的顺序被改变了。

提示:

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] 仅由小写英文字母组成。

    public int longestStrChain(String[] words) {Arrays.sort(words, Comparator.comparingInt(String::length));Map<String, Integer> map = new HashMap<>();int res = 0;for (String word : words) {int max = 0;for (int i = 0; i < word.length(); i++) {String s = word.substring(0, i) + word.substring(i + 1);if (map.containsKey(s)) {max = Math.max(max, map.get(s));}}map.put(word, max + 1);res = Math.max(res, max+1);}return res;}

在这里插入图片描述

func longestStrChain(words []string) int {sort.Slice(words, func(i, j int) bool {return len(words[i])<len(words[j])})mapx:=make(map[string]int,0)res := 0for _, word := range words {max := 0for i := 0; i < len(word); i++ {s:=word[0:i]+word[i+1:]if v,ok:=mapx[s];ok {max = getMax(max, v)}}mapx[word]= max + 1res = getMax(res, max+1)}return res
}func getMax(x,y int) int{if x>y {return x}return y
}

在这里插入图片描述

相关文章:

【Java|golang】1048. 最长字符串链

给出一个单词数组 words &#xff0c;其中每个单词都由小写英文字母组成。 如果我们可以 不改变其他字符的顺序 &#xff0c;在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB &#xff0c;那么我们认为 wordA 是 wordB 的 前身 。 例如&#xff0c;“abc” 是 “abac”…...

Hive基础和使用详解

文章目录 一、启动hive1. hive启动的前置条件2. 启动方式一: hive命令3. 方式二:使用jdbc连接hive 二、Hive常用交互命令1. hive -help 命令2. hive -e 命令3. hive -f 命令4. 退出hive窗口5. 在hive窗口中执行dfs -ls /&#xff1b; 三、Hive语法1.DDL语句1.1 创建数据库1.2 两…...

c/c++:栈帧,传值,传址,实参传值给形参,传地址指针给形参

c/c&#xff1a;栈帧&#xff0c;传值&#xff0c;传址&#xff0c;实参传值给形参&#xff0c;传地址指针给形参 2022找工作是学历、能力和运气的超强结合体&#xff0c;遇到寒冬&#xff0c;大厂不招人&#xff0c;此时学会c的话&#xff0c; 我所知道的周边的会c的同学&…...

玩元宇宙血亏后 蓝色光标梭哈AI也挺悬

蓝色光标2022年年度报告出炉&#xff0c;巨亏21.75 亿元&#xff0c;其中20.38亿亏损因商誉、无形资产及其他资产减值造成&#xff0c;而在实际亏损业务中&#xff0c;元宇宙占比不小。 蓝色光标在元宇宙领域的布局&#xff0c;主要通过三家子公司实施&#xff0c;分别为蓝色宇…...

生物---英文

标题 前言必学场景词汇及用法鸟类昆虫类哺乳类爬行类情境常用单词鸟类虫类哺乳类两栖类与爬行类分类与动物相关的习语前言 加油 必学场景词汇及用法 鸟类 1bird [b[插图]d] n.鸟bird’s-eye-view[ˈb[插图]dzaɪˌvju]adj.鸟瞰图的a bird’s-eye view鸟瞰a flock of bird…...

ENVI 国产高分2号(GF-2)卫星数据辐射定标 大气校正 影像融合

1.数据 高分2号卫星数据&#xff0c;包含&#xff1a; MSS-1\2多光谱数据&#xff0c;4m分辨率&#xff1b; Pan-1\2全色波段数据&#xff0c;0.8m分辨率。 2.处理软件 ENVI5.3 国产插件下载地址&#xff1a;ENVI App Store (geoscene.cn) 首先下载插件文件&#xff1b; …...

操作系统考试复习——第二章 进程控制 同步与互斥

进程控制一般是由OS中的原语来实现的。 大多数OS内核都包含了两大方面的功能&#xff1a; 1.支撑功能&#xff1a;1)中断处理 2)时钟管理 3)原语操作(原语操作就是原子操作。所谓原子操作就是一个操作中所有动作要不全做要不全不做) 2.资源管理功能&#xff1a;1)进程管理…...

mac gitstats查看git提交记录

一、介绍&#xff1a; 进一步来讲&#xff0c;Gitstats它是一个git仓库分析软件&#xff0c;它可以检查仓库并生成历史数据的统计信息。可以帮助你查看git仓库的提交状态&#xff0c;根据不同维度分析计算&#xff0c;并自动生成数据图表。 官网介绍&#xff1a;http://gitst…...

电脑系统错误怎么办?您可以看看这5个方法!

案例&#xff1a;电脑出现系统错误该如何解决&#xff1f; 【这几天长时间使用我的电脑&#xff0c;导致它的系统出现了错误。有没有小伙伴知道如何解决电脑系统出错的问题&#xff1f;求一个能快速解决的方法。】 电脑系统出现错误是使用电脑时难免会遇到的问题之一&#xf…...

九款顶级AI工具推荐

ChatGPT OpenAI开发的最强对话系统 地址&#xff1a;chat.openai.com ChatGPT能够在同一个会话期间内回答上下文相关的后续问题。其在短时间内引爆全球的原因在于&#xff0c;在网友们晒出的截图中&#xff0c;ChatGPT不仅能流畅地与用户对话&#xff0c;甚至能写诗、撰文、编…...

StringRedisTemplate-基本使用

StringRedisTemplate继承自RedisTemplate,在这里说明一下&#xff0c;当我们使用RedisTemplate往redis中存储java对象的时候&#xff0c;他会顺带着将该java对象的字节码文件也同时存进了内存中&#xff0c;这是为了实现自动反序列化Autowired private StringRedisTemplate red…...

ansible自动运维——ansible使用临时命令通过模块来执行任务

大家好&#xff0c;这里是天亮之前ict&#xff0c;本人网络工程大三在读小学生&#xff0c;拥有锐捷的ie和红帽的ce认证。每天更新一个linux进阶的小知识&#xff0c;希望能提高自己的技术的同时&#xff0c;也可以帮助到大家 另外其它专栏请关注&#xff1a; 锐捷数通实验&…...

python 之数据类型(四)

1、字符串&#xff08;String&#xff09; 使用双引号或者单引号中的数据&#xff0c;就是字符串 注&#xff1a;python中使用三引号时允许一个字符串跨多行&#xff0c;字符串中可以包含换行符、制表符以及其它特殊符号 a a c g print(a)运行结果&#xff1a; a c g1、下标 …...

洛谷P1345 无向图最小割点数

题意&#xff1a; 给出一副有 n n n个点&#xff0c; m m m条边的无向图&#xff0c;求出这副图的最小割点数 题意&#xff1a; 首先对于有向图&#xff0c;求他的最小割边&#xff0c;只需要令每条边的容量为 1 1 1&#xff0c;求出起点到终点的最大流就是最小割边数了。 容…...

适合程序员阅读的有用书籍:

几本适合程序员阅读的有用书籍&#xff1a; 1.《计算机程序设计艺术》(The Art of Computer Programming)是由Donald E. Knuth撰写的一系列著作&#xff0c;是计算机科学领域的经典之作。该系列著作共分为三卷&#xff0c;分别介绍了算法和计算机程序设计的基础知识和技巧。 …...

MySQL: 自动添加约束、更改(删除)表名和字段、删除表

目录 自动添加表的属性&#xff1a; 向表内插入数据&#xff1a; 查看表中的数据&#xff1a; 查看表结构&#xff1a; 查看表的详细结构&#xff1a; 更改表名和字段&#xff1a; 更改表名&#xff1a; 更改字段数据类型&#xff1a; 修改字段名&#xff1a; 添加字段…...

基于微博评论的细粒度的虚假信息识别软件

任务 目标:能检测单模态的虚假信息就可以,是个软件就可以 参考文章:基于多模态深度融合的虚假信息检测 Multi-modal deep fusion for false information detection 思路 多模态指的是多种不同类型的数据,比如图像、文本、音频等。虚假信息识别软件可以从这些不同类型的数据…...

Android 11.0 系统systemui状态栏下拉左滑显示通知栏右滑显示控制中心模块的流程分析

1.前言 在android11.0的系统rom定制化开发中,在系统原生systemui进行自定义下拉状态栏布局的定制的时候,需要在systemui下拉状态栏下滑的时候,根据下滑坐标来 判断当前是滑出通知栏还是滑出控制中心模块,所以就需要根据屏幕宽度,来区分x坐标值为多少是左滑出通知栏或者右…...

ROS学习第三十二节——xacro构建激光雷达小车

https://download.csdn.net/download/qq_45685327/87718396 在前面小车底盘基础之上&#xff0c;添加摄像头和雷达传感器。 0.底盘实现 deamo02_base.xacro <!--使用 xacro 优化 URDF 版的小车底盘实现&#xff1a;实现思路:1.将一些常量、变量封装为 xacro:property比如…...

中厂,面试就问了4道题,凉了!

你好&#xff0c;我是田哥 所谓的金三银四&#xff0c;已变成铜三铁四了。很多人基本上莫有面试机会&#xff0c;更可惜的是机会有了&#xff0c;却没有把握住。 加入我知识星球&#xff1a;免费做简历优化、简历包装、模拟面试... 今天早上&#xff0c;一个朋友和我说面试中被…...

22.轮播模块

学习要点&#xff1a; 1.轮播模块 本节课我们来开始了解 Layui 的内置模块&#xff1a;轮播模块。 一&#xff0e;轮播模块 1. 轮播模块&#xff0c;即跑马灯等轮播交互场景&#xff0c;先来看下基本设置&#xff1b; <div id"test" class"layui-carousel&qu…...

MYSQL命令小总结

一、创建查看 1.输入cmd&#xff0c;打开控制器&#xff0c;输入如下&#xff0c;打开MYSQL C:\Users\ASUS> mysql -u root -p 2.查看已有数据库 mysql> show databases; 3.建立数据库 4.使用数据库 use englishword;5.建立表单 CREATE TABLE user ( id INT primar…...

Java常见开发工具和Object类

Java是一种面向对象的编程语言&#xff0c;被广泛应用于各种应用程序和软件开发中。在Java开发过程中&#xff0c;使用一个好的开发工具可以大大提高开发效率和代码质量。Eclipse是一个功能强大、灵活易用的Java集成开发环境&#xff08;IDE&#xff09;&#xff0c;被广泛使用…...

Linux 配置YUM源(FTP方式获取软件源、使用阿里云yum源、同时使用本地源与在线源)YUM获取安装包并生成YUM软件仓库

YUM介绍 YUM&#xff08;yellow dog updater modified&#xff09; 基于RPM包构建的软件更新机制 自动解决依赖关系 yum软件仓库集中管理软件包 RPM软件包的来源 centos发布的RPM包集合第三方组织发布的RPM包集合用户自定义的RPM包集合 软件仓库的提供方式 FTP服务&#xff1a;…...

Java版工程行业管理系统源码-专业的工程管理软件-提供一站式服务

Java版工程项目管理系统 Spring CloudSpring BootMybatisVueElementUI前后端分离 功能清单如下&#xff1a; 首页 工作台&#xff1a;待办工作、消息通知、预警信息&#xff0c;点击可进入相应的列表 项目进度图表&#xff1a;选择&#xff08;总体或单个&#xff09;项目显示…...

养老保障金查询系统【GUI/Swing+MySQL】(Java课设)

系统类型 Swing窗口类型Mysql数据库存储数据 使用范围 适合作为Java课设&#xff01;&#xff01;&#xff01; 部署环境 jdk1.8Mysql8.0Idea或eclipsejdbc 运行效果 本系统源码地址&#xff1a;https://download.csdn.net/download/qq_50954361/87700421 更多系统资源库…...

国考省考行测:词句理解,词的对象指代,就近原则,主语一致法,语意语境分析上下文找出指代含义

国考省考行测&#xff1a;词句理解&#xff0c;词的对象指代&#xff0c;就近原则&#xff0c;主语一致法&#xff0c;语意语境分析上下文找出指代含义 2022找工作是学历、能力和运气的超强结合体! 公务员特招重点就是专业技能&#xff0c;附带行测和申论&#xff0c;而常规国…...

部署YUM仓库

部署YUM仓库 YUM概述软件仓库的提供方式RPM软件包的来源FTP源的配置方法本地源配置方法在线源配置方法本地源和在线源一起使用的方法数据包缓存方法 自己配置本地yum源时需要使用createrepo来生成依赖关系库 YUM概述 YUM(Yellow dog Updater Modified) 基于RPM包构建的软件更…...

SpringBoot框架(邮件发送Mail|持久层框架JPA|Extra前后端分离跨域处理|接口管理Swagger)这一篇就够了(超详细)

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;老茶icon &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开兴好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;计…...

chatGPT对话R语言

文章目录 R语言介绍R语言基本语法R语言常用函数有哪些R语言数据结构向量矩阵数组和列表数组列表 数据框因子 R如何导入数据如何在R语言中导出数据&#xff1f;R语言图形绘制描述性统计描述统计也可以这样来计算 统计推断配对设计t检验样本均数和总体均数t检验两&#xff08;独立…...