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 <= 10001 <= words[i].length <= 16words[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(nL2)，其中L是字符串的长度，substr()函数须要O(L)的工夫复杂度。
空间复杂度：O(nL)