Medium

题目描述

给你一个单词数组 words，其中每个单词都由小写英文字母组成。

如果我们可以不改变其他字符的顺序的情况下在 wordA 的任何地方添加恰好一个字母使其变成 wordB，那么我们认为 wordA 是 wordB 的前身。

  • 例如，"abc" 是 "abac" 的前身，而 "cba" 不是 "bcad" 的前身。

词链是单词 [word1, word2, ..., wordk] 组成的序列，k >= 1，其中 word1 是 word2 的前身，word2 是 word3 的前身，依此类推。一个单词通常是 k == 1 的单词链。

从给定单词列表 words 中选择单词组成词链，返回最长可能的词链的长度。

示例 1：

输入：words = ["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 ["a","ba","bda","bdca"]

示例 2：

输入：words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
输出：5
解释：所有的单词都可以放入单词链 ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"]

示例 3：

输入：words = ["abcd","dbqca"]
输出：1
解释：单词链 ["abcd"] 是最长的单词链之一。
["abcd","dbqca"] 不是一个有效的单词链，因为字母的顺序被改变了。

提示：

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 16
  • words[i] 只由小写英文字母组成。

解题思路

这道题可以使用动态规划来解决。核心思路是：

  1. 排序优化：首先按照字符串长度对单词数组进行排序，这样我们可以保证在处理某个单词时，所有可能的前身都已经被处理过了。

  2. 状态定义：使用哈希表 dp，其中 dp[word] 表示以 word 结尾的最长字符串链的长度。

  3. 状态转移：对于每个单词，我们尝试删除其中的每一个字符，得到一个新的字符串。如果这个新字符串在之前出现过（即在 dp 中存在），那么当前单词可以接在这个字符串后面形成更长的链。

  4. 逆向思考：题目提示我们可以通过删除字符来反向构建链。对于每个单词，我们删除一个字符得到可能的前身，然后更新当前单词的最大链长度。

  5. 边界条件：每个单词本身都可以构成长度为1的链。

时间复杂度主要来自于排序和对每个单词的每个字符进行删除操作。空间复杂度主要是哈希表存储每个单词的最大链长度。

代码实现

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& a, const string& b) {
            return a.length() < b.length();
        });
        
        unordered_map<string, int> dp;
        int maxLength = 1;
        
        for (const string& word : words) {
            dp[word] = 1;
            for (int i = 0; i < word.length(); i++) {
                string predecessor = word.substr(0, i) + word.substr(i + 1);
                if (dp.find(predecessor) != dp.end()) {
                    dp[word] = max(dp[word], dp[predecessor] + 1);
                }
            }
            maxLength = max(maxLength, dp[word]);
        }
        
        return maxLength;
    }
};

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)
        dp = {}
        max_length = 1
        
        for word in words:
            dp[word] = 1
            for i in range(len(word)):
                predecessor = word[:i] + word[i+1:]
                if predecessor in dp:
                    dp[word] = max(dp[word], dp[predecessor] + 1)
            max_length = max(max_length, dp[word])
        
        return max_length

public class Solution {
    public int LongestStrChain(string[] words) {
        Array.Sort(words, (a, b) => a.Length.CompareTo(b.Length));
        
        Dictionary<string, int> dp = new Dictionary<string, int>();
        int maxLength = 1;
        
        foreach (string word in words) {
            dp[word] = 1;
            for (int i = 0; i < word.Length; i++) {
                string predecessor = word.Substring(0, i) + word.Substring(i + 1);
                if (dp.ContainsKey(predecessor)) {
                    dp[word] = Math.Max(dp[word], dp[predecessor] + 1);
                }
            }
            maxLength = Math.Max(maxLength, dp[word]);
        }
        
        return maxLength;
    }
}

var longestStrChain = function(words) {
    words.sort((a, b) => a.length - b.length);
    
    const dp = new Map();
    let maxLength = 1;
    
    for (const word of words) {
        dp.set(word, 1);
        for (let i = 0; i < word.length; i++) {
            const predecessor = word.slice(0, i) + word.slice(i + 1);
            if (dp.has(predecessor)) {
                dp.set(word, Math.max(dp.get(word), dp.get(predecessor) + 1));
            }
        }
        maxLength = Math.max(maxLength, dp.get(word));
    }
    
    return maxLength;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × m² × log n)，其中 n 是单词数量，m 是单词的平均长度。排序需要 O(n log n)，对每个单词需要尝试删除 m 个字符，每次删除操作需要 O(m) 时间构造新字符串
空间复杂度O(n × m)，哈希表存储所有单词及其对应的最长链长度，每个单词长度最多为 m