写点什么

最长字符串链,什么是“词链”?

作者:掘金安东尼
  • 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
用户头像

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

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

评论

发布
暂无评论
最长字符串链,什么是“词链”?_算法_掘金安东尼_InfoQ写作社区