[Leetcode 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: [“a”,”b”,”ba”,”bca”,”bda”,”bdca”]
Output: 4
Explanation: one of the longest word chain is “a”,”ba”,”bda”,”bdca”.

 

Note:

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

解题思路

这道题可以用动态规划的思路来解。

先将给我们的词按长度从小到大排列，然后用一个哈希表记录能从小到大变化到一个词的最大长度。也就是说，key是一个词，value是从小到大能变换到这个词的最大长度。

我们按词的长度从小到大遍历所有的词，对于每一个词cur，遍历这个词的每一个可能的前一个词prev，若存在在哈希表中，则dp[cur] = max(dp[cur], dp[prev] + 1)。这也就是我们的状态转移方程。

最后我们查找哈希表中的最大值，就是我们要的答案。

示例代码 (cpp)

class Solution {
private:
    // static bool compare(const string &s1, const string &s2) {
    //     return s1.length() < s2.length();
    // }
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b){return a.size() < b.size();});
        // sort(words.begin(), words.end(), compare);
        unordered_map<string, int> dp;
        int res = 0;
        for (const string& cur : words) {
            for (int i = 0; i < cur.length(); i++) {
                auto prev = cur.substr(0, i) + cur.substr(i + 1);
                dp[cur] = max(dp[cur], dp[prev] + 1);
            }
            res = max(res, dp[cur]);
        }
        return res;
    }
};

示例代码 (java)

class Solution {
    public int longestStrChain(String[] words) {
        Map<String, Integer> dp = new HashMap<>();
        Arrays.sort(words, (a, b)->a.length() - b.length());
        int res = 0;
        for (String word : words) {
            int best = 0;
            for (int i = 0; i < word.length(); ++i) {
                String prev = word.substring(0, i) + word.substring(i + 1);
                best = Math.max(best, dp.getOrDefault(prev, 0) + 1);
            }
            dp.put(word, best);
            res = Math.max(res, best);
        }
        return res;
    }
}

示例代码 (python)

class Solution:
    def longestStrChain(self, words):
        dp = {}
        for w in sorted(words, key=len):
            dp[w] = max(dp.get(w[:i] + w[i + 1:], 0) + 1 for i in range(len(w)))
        return max(dp.values())

复杂度分析

时间复杂度: 假设一共有N个词，词的平均长度是L，时间复杂度是 O(NlogN + NL^2)
空间复杂度: O(NL)

归纳总结

我们在Youtube上更新了视频讲解，欢迎关注！