​力扣解法汇总1048. 最长字符串链

news/2024/11/13 22:46:12/

 目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

给出一个单词数组 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] 仅由小写英文字母组成。

解题思路:

* 解题思路:
* 构建一个Map<Integer, Map<String, Integer>>类型的map,key代表字符串长度,value的Map代表每个字符串的单词链最长长度。
* 然后按照单词的长度分组。
* 分别遍历单词的长度length分别遍历,每次遍历时,去查找length-1长度的map中,是否有满足要求的,如果有,则在其长度上+1,如果没有,则长度设置为1。

代码:

public class Solution1048 {int mMax = 1;public int longestStrChain(String[] words) {Arrays.sort(words, new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {return o1.length() - o2.length();}});TreeMap<Integer, List<String>> tree = new TreeMap<>();for (String str : words) {int length = str.length();List<String> strings = tree.get(length);if (strings == null) {strings = new ArrayList<>();tree.put(length, strings);}strings.add(str);}Map<Integer, Map<String, Integer>> map = new HashMap<>();for (int i = 0; i <= 16; i++) {map.put(i, new HashMap<>());}for (int length : tree.keySet()) {List<String> strings = tree.get(length);search(length, strings, map);}return mMax;}public void search(int length, List<String> list, Map<Integer, Map<String, Integer>> map) {Map<String, Integer> shortMap = map.get(length - 1);Map<String, Integer> longMap = map.get(length);for (String str : list) {for (String key : shortMap.keySet()) {if (isMatch(key, str)) {int newLength = shortMap.get(key) + 1;longMap.put(str, Math.max(newLength, longMap.getOrDefault(str, 0)));mMax = Math.max(mMax, newLength);}}if (longMap.get(str) == null) {longMap.put(str, 1);}}}public boolean isMatch(String shortStr, String longStr) {if ((longStr.length() - shortStr.length()) != 1) {return false;}char[] chars1 = shortStr.toCharArray();char[] chars2 = longStr.toCharArray();int num = 0;for (int i = 0; i < chars2.length; i++) {if (i - num == chars1.length) {return true;}if (chars1[i - num] == chars2[i]) {continue;}num++;if (num > 1) {return false;}}return true;}
}


http://www.ppmy.cn/news/55085.html

相关文章

Qt 制作小程序登录系统(超详细)

在这里我使用的是 Qt4, 在 windows 平台上来实现的。 文章目录 前言一、基本部件的创建二、主界面的绘制&#xff1a;1. 设置各部件文本&#xff1a;2. 界面布局&#xff1a; 三、 信号处理机制四、Qt4 显示汉字:1. 出现乱码现象2. 解决方法 五、设置标题栏的小图标总结 前言 …

从零开始学习Linux运维,成为IT领域翘楚(三)

文章目录 &#x1f525;Linux超级用户与伪用户&#x1f525;Linux文件基本属性&#x1f525;Linux权限字与权限操作 &#x1f525;Linux超级用户与伪用户 Linux下用户分为三类&#xff1a;超级用户、普通用户、伪用户 ⭐ 超级用户&#xff1a;用户名为root&#xff0c;具有一切…

数据可视化大屏的页面布局以及自适应

在做数据可视化大屏之前&#xff0c;我们需要考虑到页面的布局问题以及页面缩放自适应问题&#xff0c;下面分别就这两个方面讲解。 页面布局 类似这种页面区块的明显划分&#xff0c;常用的布局方式有两种&#xff1a; 1、flex布局 2、grid布局 grid布局 grid布局可以按区块…

springboot+nodejs+vue众筹项目管理系统平台系统

筹资人&#xff08;企业&#xff09;&#xff1a; 1&#xff0c;可以后台注册并登录&#xff0c;发布项目情况&#xff0c;众筹项目需要管理员审核通过后才能展现在前台&#xff0c;没有审核或者审核不通过不会在前台展示&#xff1b; 众筹项目包括项目名称&#xff0c;项目分类…

所有Gcc版本对C和C++的支持情况(超详细版本)

在最近接触的新的项目&#xff0c;由于技术使用为C98风格实现&#xff0c;遇到一个问题需要加锁解决&#xff0c;本能反应用lock_guradmutex解决&#xff0c;但是没设置CFLAGS为C11标准&#xff0c;不确定当前gcc编译器默认支持的C和C标准是什么&#xff0c;索性就一把都研究透…

图像修补论文阅读:MAT算法笔记

标题&#xff1a;MAT: Mask-Aware Transformer for Large Hole Image Inpainting 会议&#xff1a;CVPR2022 论文地址&#xff1a;https://ieeexplore.ieee.org/document/9879508/ 官方代码&#xff1a;https://github.com/fenglinglwb/MAT 作者单位&#xff1a;香港中文大学、…

ElasticSearch-PYTHON

一、常规操作 1.1 建立连接 from elasticsearch import Elasticsearch es Elasticsearch([{"host": "主机名", "port": 端口}],http_auth(账号, 密码))1.2 在ES中插入数据 def add_one_index(body):es.index(index"test_index", d…

前端:记录一次monorepo的改造过程

itravel-web 使用 monorepo 管理项目 adminweb amin pnpm admin:devpnpm admin:buildweb pnpm web:devpnpm web:buildpnpm web:build:devpnpm monorepo 改造原有项目记录 解决方案 建立 monorepo 项目文件夹pnpm init 初始化项目建立 packages 文件夹建立 pnpm-workspac…