# 1048. Longest String Chain

Given a list of words, each word consists of English lowercase letters.

Let’s say `word1` is a predecessor of `word2` if and only if we can add exactly one letter anywhere in `word1` to make it equal to `word2`.  For example, `"abc"` is a predecessor of `"abac"`.

A *word chain *is a sequence of words `[word_1, word_2, ..., word_k]` with `k >= 1`, where `word_1` is a predecessor of `word_2``word_2` is a predecessor of `word_3`, and so on.

Return the longest possible length of a word chain with words chosen from the given list of `words`.

Example 1:

``````Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chain is "a","ba","bda","bdca".
``````

Example 2:

``````Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
``````

Constraints:

• `1 <= words.length <= 1000`
• `1 <= words[i].length <= 16`
• `words[i]` only consists of English lowercase letters.

``````class Solution {
public:
int longestStrChain(vector<string>& words) {
int n = words.size(), res = 1;
sort(words.begin(), words.end(), [](string& a, string &b){
return a.size() < b.size();
});
vector<int> dp(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (words[j].size() + 1 < words[i].size()) break;
if (words[j].size() == words[i].size()) continue;
if (helper(words[j], words[i])) {
dp[i] = max(dp[i], dp[j] + 1);
res = max(res, dp[i]);
}
}
}
return res;
}
bool helper(string word1, string word2) {
int m = word1.size(), n = word2.size(), i = 0;
for (int j = 0; j < n; ++j) {
if (word2[j] == word1[i]) ++i;
}
return i == m;
}
};
``````

``````class Solution {
public:
int longestStrChain(vector<string>& words) {
int n = words.size(), res = 1;
sort(words.begin(), words.end(), [](string& a, string& b){ return a.size() < b.size(); });
unordered_map<string, int> dp;
for (string word : words) {
dp[word] = 1;
for (int i = 0; i < word.size(); ++i) {
string pre = word.substr(0, i) + word.substr(i + 1);
if (dp.count(pre)) {
dp[word] = max(dp[word], dp[pre] + 1);
res = max(res, dp[word]);
}
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1048

Longest Arithmetic Subsequence

https://leetcode.com/problems/longest-string-chain/

https://leetcode.com/problems/longest-string-chain/discuss/294890/JavaC%2B%2BPython-DP-Solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation