【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 ,其中每个单词都由小写英文字母组成。 如果我们可以 不改变其他字符的顺序 ,在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ,那么我们认为 wordA 是 wordB 的 前身 。 例如,“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 /; 三、Hive语法1.DDL语句1.1 创建数据库1.2 两…...
c/c++:栈帧,传值,传址,实参传值给形参,传地址指针给形参
c/c:栈帧,传值,传址,实参传值给形参,传地址指针给形参 2022找工作是学历、能力和运气的超强结合体,遇到寒冬,大厂不招人,此时学会c的话, 我所知道的周边的会c的同学&…...
玩元宇宙血亏后 蓝色光标梭哈AI也挺悬
蓝色光标2022年年度报告出炉,巨亏21.75 亿元,其中20.38亿亏损因商誉、无形资产及其他资产减值造成,而在实际亏损业务中,元宇宙占比不小。 蓝色光标在元宇宙领域的布局,主要通过三家子公司实施,分别为蓝色宇…...
生物---英文
标题 前言必学场景词汇及用法鸟类昆虫类哺乳类爬行类情境常用单词鸟类虫类哺乳类两栖类与爬行类分类与动物相关的习语前言 加油 必学场景词汇及用法 鸟类 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号卫星数据,包含: MSS-1\2多光谱数据,4m分辨率; Pan-1\2全色波段数据,0.8m分辨率。 2.处理软件 ENVI5.3 国产插件下载地址:ENVI App Store (geoscene.cn) 首先下载插件文件; …...
操作系统考试复习——第二章 进程控制 同步与互斥
进程控制一般是由OS中的原语来实现的。 大多数OS内核都包含了两大方面的功能: 1.支撑功能:1)中断处理 2)时钟管理 3)原语操作(原语操作就是原子操作。所谓原子操作就是一个操作中所有动作要不全做要不全不做) 2.资源管理功能:1)进程管理…...
mac gitstats查看git提交记录
一、介绍: 进一步来讲,Gitstats它是一个git仓库分析软件,它可以检查仓库并生成历史数据的统计信息。可以帮助你查看git仓库的提交状态,根据不同维度分析计算,并自动生成数据图表。 官网介绍:http://gitst…...
电脑系统错误怎么办?您可以看看这5个方法!
案例:电脑出现系统错误该如何解决? 【这几天长时间使用我的电脑,导致它的系统出现了错误。有没有小伙伴知道如何解决电脑系统出错的问题?求一个能快速解决的方法。】 电脑系统出现错误是使用电脑时难免会遇到的问题之一…...
九款顶级AI工具推荐
ChatGPT OpenAI开发的最强对话系统 地址:chat.openai.com ChatGPT能够在同一个会话期间内回答上下文相关的后续问题。其在短时间内引爆全球的原因在于,在网友们晒出的截图中,ChatGPT不仅能流畅地与用户对话,甚至能写诗、撰文、编…...
StringRedisTemplate-基本使用
StringRedisTemplate继承自RedisTemplate,在这里说明一下,当我们使用RedisTemplate往redis中存储java对象的时候,他会顺带着将该java对象的字节码文件也同时存进了内存中,这是为了实现自动反序列化Autowired private StringRedisTemplate red…...
ansible自动运维——ansible使用临时命令通过模块来执行任务
大家好,这里是天亮之前ict,本人网络工程大三在读小学生,拥有锐捷的ie和红帽的ce认证。每天更新一个linux进阶的小知识,希望能提高自己的技术的同时,也可以帮助到大家 另外其它专栏请关注: 锐捷数通实验&…...
python 之数据类型(四)
1、字符串(String) 使用双引号或者单引号中的数据,就是字符串 注:python中使用三引号时允许一个字符串跨多行,字符串中可以包含换行符、制表符以及其它特殊符号 a a c g print(a)运行结果: a c g1、下标 …...
洛谷P1345 无向图最小割点数
题意: 给出一副有 n n n个点, m m m条边的无向图,求出这副图的最小割点数 题意: 首先对于有向图,求他的最小割边,只需要令每条边的容量为 1 1 1,求出起点到终点的最大流就是最小割边数了。 容…...
适合程序员阅读的有用书籍:
几本适合程序员阅读的有用书籍: 1.《计算机程序设计艺术》(The Art of Computer Programming)是由Donald E. Knuth撰写的一系列著作,是计算机科学领域的经典之作。该系列著作共分为三卷,分别介绍了算法和计算机程序设计的基础知识和技巧。 …...
MySQL: 自动添加约束、更改(删除)表名和字段、删除表
目录 自动添加表的属性: 向表内插入数据: 查看表中的数据: 查看表结构: 查看表的详细结构: 更改表名和字段: 更改表名: 更改字段数据类型: 修改字段名: 添加字段…...
基于微博评论的细粒度的虚假信息识别软件
任务 目标:能检测单模态的虚假信息就可以,是个软件就可以 参考文章:基于多模态深度融合的虚假信息检测 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 在前面小车底盘基础之上,添加摄像头和雷达传感器。 0.底盘实现 deamo02_base.xacro <!--使用 xacro 优化 URDF 版的小车底盘实现:实现思路:1.将一些常量、变量封装为 xacro:property比如…...
中厂,面试就问了4道题,凉了!
你好,我是田哥 所谓的金三银四,已变成铜三铁四了。很多人基本上莫有面试机会,更可惜的是机会有了,却没有把握住。 加入我知识星球:免费做简历优化、简历包装、模拟面试... 今天早上,一个朋友和我说面试中被…...
SSD用久了为啥会变慢?深入NAND Flash的‘写放大’与‘磨损均衡’,教你看懂SMART数据避坑
SSD性能下降的真相:从写放大到磨损均衡的深度解析 你是否遇到过这样的困扰——新买的SSD速度飞快,但用了一段时间后,系统响应明显变慢,开机时间延长,文件传输速度大不如前?这种现象并非偶然,而是…...
光流法在气象雷达中的应用:从原理到外推实践
光流法在气象雷达中的应用:从原理到外推实践 气象雷达作为现代气象监测的核心工具,其回波数据蕴含着丰富的天气系统动态信息。如何从这些看似静态的图像序列中提取运动规律,进而预测未来短时内的天气变化,一直是气象学界和工程界关…...
3大核心优势!猫抓视频捕获工具让流媒体解析效率提升100%
3大核心优势!猫抓视频捕获工具让流媒体解析效率提升100% 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 猫抓浏览器扩展是一款专业的网…...
德意志飞机通过全球协作升级支线航空驾驶舱人机工学
2026年1月15日 —— 作为总部位于德国舍瑙的MAFELEC集团旗下成员,COMTRONIC GmbH近五十年来一直是航空航天领域人机界面(HMI)解决方案领域值得信赖的供应商。凭借在照明面板、定制键盘及先进光学技术方面的深厚积淀,COMTRONIC长期…...
RAG系统的需求分析
这个是一个基于私有知识库的智能对话平台,允许用户上传文档构建专属知识库,并通过自然语言交互的方式查询和获取知识。它结合了大语言模型和向量检索技术,让用户通过对话的形式与自己的知识库进行高效交互应用场景个人用户场景:学习助手&…...
ARL灯塔扫不出指纹?手把手教你用Python脚本批量导入指纹库,提升资产识别准确率
ARL灯塔指纹识别优化实战:Python脚本批量导入与精准率提升指南 资产侦察灯塔(ARL)作为渗透测试领域的重要工具,其核心价值在于准确识别目标资产的技术特征。然而许多中级用户发现,默认指纹库在面对特定行业或新型资产…...
如何用GPU加速的MediaPipe TouchDesigner插件实现实时视觉交互
如何用GPU加速的MediaPipe TouchDesigner插件实现实时视觉交互 【免费下载链接】mediapipe-touchdesigner GPU Accelerated MediaPipe Plugin for TouchDesigner 项目地址: https://gitcode.com/gh_mirrors/me/mediapipe-touchdesigner MediaPipe TouchDesigner插件是一…...
[AI/应用/MCP] MCP Server/Tool 开发指南
1. 智能软件工程的范式转移:从库集成到原生框架演进 在生成式人工智能(Generative AI)从单纯的文本生成向具备自主规划与执行能力的“代理化(Agentic)”系统跨越的过程中,.NET 生态系统正在经历一场自该平台…...
PID控制在自动循迹小车中的实战应用与参数整定指南
PID控制在自动循迹小车中的实战应用与参数整定指南 当你在实验室里第一次看到自己设计的自动循迹小车歪歪扭扭地沿着黑线前进时,那种既兴奋又挫败的感觉一定记忆犹新。为什么理论上完美的PID算法,在实际应用中却总是出现超调、振荡或者响应迟缓ÿ…...
保姆级避坑指南:在Ubuntu 22.04上为ROS2 Humble编译OpenCV 4.2.0和cv_bridge
深度解析:Ubuntu 22.04下ROS2 Humble与OpenCV 4.2.0的精准版本匹配实战 当视觉SLAM遇上ROS2生态,版本依赖就像一场精密的外科手术。本文将带你穿透ORB-SLAM3等视觉算法与ROS2 Humble环境整合时的核心痛点——特别是OpenCV 4.2.0与cv_bridge的版本锁定机…...
