假设我们有一个单词列表，这里的每个单词都由小写字母组成。因此，当且仅当我们可以在word1的任意位置添加正好一个字母使其等于word2时，一个单词word1才是另一个单词word2的前身。举个例子，“ abc”是“ abac”的前身。现在，单词链是单词[word_1，word_2，...，word_k]的序列，且k> = 1，其中word_1是word_2的前身，word_2是word_3的前身，依此类推。我们必须使用从给定单词列表中选择的单词找到单词链的最大可能长度。
因此，如果输入类似于：[“ a”，“ b”，“ ba”，“ bca”，“ bda”，“ bdca”]，则结果将为4，因为最长链之一将为[“ a”，“ ba”，“ bda”，“ bdca”]。
为了解决这个问题，我们将遵循以下步骤-
定义一个映射dp，n：=单词数组的大小
根据长度对单词数组进行排序
ret：= 0
对于i，范围为0 tn n – 1
单词：=（单词[i]的子字符串，从0到j – 1）串联（单词[i]的子字符串，从j + 1到结尾）
最好的：=最好的最大值，dp [word] +1
最好：= 0
对于范围从0到单词[i] – 1的长度的j
dp [words [i]]：=最佳
ret：=（ret，dp [words [i]]）的最大值
返回ret
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(string s1, string s2){
return s1.size() < s2.size();
}
int longestStrChain(vector<string>& words) {
unordered_map <string, int> dp;
int n = words.size();
sort(words.begin(), words.end(), cmp);
int ret = 0;
for(int i = 0; i < n; i++){
int best = 0;
for(int j = 0; j < words[i].size(); j++){
string word = words[i].substr(0, j) +
words[i].substr(j + 1);
best = max(best, dp[word] + 1);
}
dp[words[i]] = best;
ret = max(ret, dp[words[i]]);
}
return ret;
}
};
main(){
vector<string> v = {"a","b","ba","bca","bda","bdca"};
Solution ob;
cout << (ob.longestStrChain(v));
}["a","b","ba","bca","bda","bdca"]
输出结果
4