关于算法:每日一题最长字符串链

1048. 最长字符串链

关键词：动静布局、线性 dp

题目起源：1048. 最长字符串链 – 力扣（Leetcode）

题目形容

 T 动静布局
 T 线性 dp

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

如果咱们能够 不扭转其余字符的程序 ，在 wordA 的任何中央增加 恰好一个 字母使其变成 wordB，那么咱们认为 wordA 是 wordB 的 前身。

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

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

从给定单词列表 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"].

输出：words = ["abcd","dbqca"]
输入：1
解释：字链 ["abcd"] 是最长的字链之一。["abcd"，"dbqca"]不是一个无效的单词链，因为字母的程序被扭转了。

数据范畴
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i]` 仅由小写英文字母组成

问题剖析

类比最长递增子序列，设 f(s)= 以字符串 s 结尾的词链的最长长度，则 f(s)=max{f(ps)+1 }，其中，ps 为 s 去除一个字符后失去的子串。

为了保障在解决 s 时，其前身全已被解决，须要将字符串按长度从小到大排序（前身的长度肯定小于 s 的长度），因为可能存在反复字符串，还须要去重，以防止不必要的计算。

代码实现

int longestStrChain(vector<string> &words) {
    // 按字符串长度排序
    // 保障在解决每个字符串时，其前身已被解决过
    sort(words.begin(), words.end(), [](const auto &s1, const auto &s2) {return s1.size() < s2.size();});

    int res = 0;
    unordered_map<string, int> f;
    for (auto &s: words) {
        // 存在反复的 s
        if (f.find(s) != f.end())continue;
        // dp
        int curLen = 0;
        for (int i = 0, l = s.size(); i < l; i++) {auto t = f.find(s.substr(0, i) + s.substr(i + 1));
            if (t != f.end())curLen = max(t->second, curLen);
        }
        // 保护最大值
        res = max(f[s] = curLen + 1, res);
    }
    return res;
}

工夫复杂度：O(nL²)，其中 L 是字符串的长度，substr()函数须要 O(L)的工夫复杂度。

空间复杂度：O(nL)