[LeetCode] 1048. Longest String Chain

[grandyang]

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.

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

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