Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork739
Description
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: 4Explanation: One of the longest word chain is "a","ba","bda","bdca".Example 2:
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]Output: 5Constraints:
1 <= words.length <= 10001 <= words[i].length <= 16words[i]only consists of English lowercase letters.
这道题给了一个单词数组，定义了一种前任关系，说是假如在 word1 中任意位置加上一个字符，能变成 word2 的话，那么 word1 就是 word2 的前任，实际上 word1 就是 word2 的一个子序列。现在问在整个数组中最长的前任链有多长，暴力搜索的话会有很多种情况，会产生大量的重复计算，所以会超时。这种玩数组求极值的题十有八九都是用动态规划 Dynamic Programming 来做的，这道题其实跟之前那道Longest Arithmetic Subsequence 求最长的等差数列的思路是很像的。首先来定义 dp 数组，这里用一个一维的数组就行了，其中 dp[i] 表示 [0, i] 区间的单词的最长的前任链。下面来推导状态转移方程，对于当前位置的单词，需要遍历前面所有的单词，这里需要先给单词按长度排个序，因为只有长度小1的单词才有可能是前任，所以只需要遍历之前所有长度正好小1的单词，若是前任关系，则用其 dp 值加1来更新当前 dp 值即可。判断前任关系可以放到一个子数组中来做，其实就是检测是否是子序列，没啥太大的难度，参见代码如下：
解法一：
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; }};论坛上的高分解法在检验是否是前任时用了一种更好的方法，不是检测子序列，而是将当前的单词，按顺序每次去掉一个字符，然后看剩下的字符串是否在之前出现过，是的话就说明有前任，用其 dp 值加1来更新当前 dp 值，这是一种更巧妙且简便的方法。这里由于要快速判断前任是否存在，所以不是用的 dp 数组，而是用了个 HashMap，对于每个遍历到的单词，按顺序移除掉每个字符，若剩余的部分在 HashMap 中，则更新 dp 值和结果 res，参见代码如下：
解法二：
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 同步地址:
类似题目：
Longest Arithmetic Subsequence
参考资料：
https://leetcode.com/problems/longest-string-chain/
https://leetcode.com/problems/longest-string-chain/discuss/294890/JavaC%2B%2BPython-DP-Solution