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

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

给出一个单词数组 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;
};

OK，以上便是本篇分享~

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