最长字符串链，什么是“词链”？

作者：掘金安东尼

2022 年 8 月 26 日
广东
本文字数：860 字
阅读完需：约 3 分钟

首先有一个 “前身” 的概念需要去理解：

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

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

例如，"abc" 是 "abac" 的前身，而 "cba" 不是 "bcad" 的前身

其次，来理解什么是 “词链”：

词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的单词链。

OK，还是挺好理解的吧~~

题目：

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

比如：

输入：words = ["a","b","ba","bca","bda","bdca"]输出：4解释：最长单词链之一为 ["a","ba","bda","bdca"]
输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]输出：5解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].

复制代码

解题思路：

先将单词按长度升序排列。然后遍历每个单词。用一个哈希表记录每个单词作为词链最后一个单词时的最大长度。

判断该单词去掉一个字符后是否存在与单词表中，如果存在，说明可构成词链。判断更新该单词哈希值。

返回最大的哈希值即可。

JavaScript 实现：

var longestStrChain = function(words) {    words.sort((a, b) => a.length - b.length);    const M = new Map();    let res = 1;    for (let s of words) {        if (M.has(s)) continue;  // 重复        M.set(s, 1);        for (let i = 0; i < s.length; i++) {            if (i > 0 && s[i] === s[i - 1]) continue;  // 重复            let t = s.substr(0, i) + s.substr(i + 1);            if (M.has(t) && M.get(t) >= M.get(s)) {                M.set(s, M.get(t) + 1);            }        }        res = Math.max(res, M.get(s));    }    return res;};

复制代码

<hr>

OK，以上便是本篇分享~

我是掘金安东尼，输出暴露输入，技术洞见生活，再会~~

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/951baaf5b15381aeba3000adb】。文章转载请联系作者。

掘金安东尼

关注

安东尼陪你度过漫长编程岁月~ 2022.07.14 加入

社会我瓜哥，人狠话不多😎 微信 anthony1453，加我交个朋友😎 正联合【机械工业出版社】出版《程序员成长手册》，敬请期待😎 真正的大师，永远怀着一颗学徒的心（易）😎

发布

暂无评论

创作场景

最长字符串链，什么是“词链”？

掘金安东尼

评论