1048. 最长字符串链
给出一个单词数组 words ，其中每个单词都由小写英文字母组成。
如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。
- 例如，
"abc"是"abac"的 前身 ，而"cba"不是"bcad"的 前身
词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的 单词链 。
从给定单词列表 words 中选择单词组成词链，返回 词链的 最长可能长度 。
示例 1：
输入：words = ["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 ["a","ba","bda","bdca"]
题解
排序 + 哈希表
根据题目描述，字符串链中的单词必须按照长度递增的顺序排列。因此，我们首先对数组 words 中的字符串按照长度进行升序排序。在排好序的数组中，如果字符串 a 是字符串 b 的前身，那么字符串 a 的长度一定是字符串 b 的长度减去 1。
我们可以使用哈希表 d 存储排好序的数组中的每个字符串的最长字符串链长度。
接下来，遍历数组 words 中的每个字符串 s，计算出它的所有前身字符串 t，每一个前身字符串 t 是将字符串 s 中的一个字符删除后得到的。如果哈希表中存在字符串 t，那么我们就能够用 d[t]+1 更新 d[s]，即 d[s]=max(d[s],d[t]+1)。然后我们更新答案为所有 d[s] 中的最大值。
遍历结束后，返回答案即可。
代码
class Solution {
public:
int longestStrChain(vector& words) {
// 将单词按照长度递增排序
sort(words.begin(), words.end(), [](auto &a, auto &b) { return a.size() < b.size(); });
int ans = 0;
unordered_map d; // 哈希表 d 存储以某个单词为链尾的最长链长度
for (auto &s : words) {
int x = 1; // 将自己看作一个长度为 1 的链
for (int i = 0; i < s.size(); ++i) {
// 枚举 s 中每个位置，假设删掉该位置上的字符后的字符串为 t
string t = s.substr(0, i) + s.substr(i + 1);
x = max(x, d[t] + 1); // 更新以 s 为链尾的最长链长度
}
d[s] = x; // 更新哈希表
ans = max(ans, x);
}
return ans; // 返回最长链长度
}
};