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_2word_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.

这道题给了一个单词数组,定义了一种前任关系,说是假如在 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 同步地址:

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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation