LeetCode 1048. Longest String Chain

@(LeetCode)

问题描述



给定一个单词列表，每个单词包含小写英文字母。



如果能在单词 word1 的任一位置插入一个字符，使得其与 word2 相等，我们把 word1 称之为 word2 的前驱。比如 abc 是 abac 的前驱。



一个单词链是指一组单词 [word_1, word_2, ..., word_k]，其中 k > 1，满足 word_1 是 word_2 的前驱，word_2 是 word_3 的前驱，以此类推。



要求从给定的单词列表 words 中，返回最长的单词链。



栗 1：

输入：["a","b","ba","bca","bda","bdca"]
输出：4
解释：

其中一条最长的单词链为：
a -> ba -> bda -> bdca



注意：

1. 1 <= words.length <= 1000

2. 1 <= words[i].length <= 16

3. word[i] 只包含小写英文字母



想看英文原文的戳这里。

解题思路



由题意可知，如果 word1 是 word2 的前驱，那么 word1 的长度必定比 word2 小 1。



那么单词链接的长度只可能是： len -> len+1 -> len+2 -> ...，依次递增。



所以很容易想到的做法是将单词以长度进行分组，如下所示。

{
	1: [word1, word2],
	2: [word3, word4, word5],
	3: [word6],
	...
}



但想要得到最大的链接长度，就得计算出所有单词的链接长度，取最大值。



但是每个单词的前驱可能有多个，那么需要计算出其所有可能的链接组合长度，再比较得出该单词的最大链接长度。



所以此题的关键点在于：求出单词的最大链接长度，即计算每个单词所有可能的链接长度，取其最大值。这里我们将单词长度分组以层的概念进行描述，每层的单词长度相同。



下面我们来介绍两种解法。

解法 1



很显然，以最后一层单词为起点的链接长度肯定为 1，因为其后没有可链接的单词。



在倒数第二层中，若单词 w1 是最后一层中单词 w2 的前驱，则其可能存在的长度为 2，否则为 1。



在倒数第三层中，若单词 w1 是倒数第二层中单词 w2 的前驱，而 w2 的链接长度可能为 2 或者 1。

• 若 w2 的链接长度为 2，则长度为 3。

• 若 w2 的链接长度为 1，则长度为 2。

• 若 w1 不是任何单词的前驱，则长度为 1。



...



以此类推，在倒数第 i 层中，若单词 w1 是倒数第 i-1 层中单词 w2 的前驱，则其中一种可能的长度为 「w2 的链接长度 + 1」。



而 w1 可能是倒数 i-1 层中 n 个单词的前驱，因此需要计算 n 个可能的链接长度，再取最大值。



总结成公式如下：

// f 表示计算链接长度函数
// word 表示某个单词，i 表示第 i 层
// word_1 表示单词，i + 1 表示第 i+1 层
// word 为 word_n 的前驱
f(word, i) = max(f(word_1, i+1), f(word_2, i+1), ..., f(word_n, i+1)) + 1

// 但如果不是任何单词的前驱，则为 1
f(word, i) = 1



那么如何计算 w1 是否为 w2 的前驱呢？



只需同时遍历 w1 和 w2，如果遇到不相等的字符，则说明 w1 要插入该字符，w2 的 index 后移一位。若后续碰到不相等的字符，则说明不为前驱，否则为其前驱。



代码实现可点此查看。



了解上述理论后，实现就不难了。因为我们已经将单词以长度进行分组，所以很容易得到上一层的所有单词，进行遍历计算即可。



这里，我提供了两种实现方式，非递归版和递归版。有兴趣的同学可点击链接进行查看。

解法 2



以上解法是从后往前的方式计算，即先计算长度最大的单词。



我们还可以通过另外一种方式，即从前往后。但注意这里单词的链接长度计算是以该单词结束，而解法 1 是以该单词为起点。



由于单词长度最大为 16，即使完全穷举出某个单词的所有前驱，也只有 16 种，效率上可能会更优。解法 1 是遍历下一层的所有单词来计算。



推导公式跟解法 1 中的大同小异。



代码也比较简洁，以下是从 讨论区 copy 的 java 代码。



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;
}



总结一下，这道题属于动态规划类，即在前面结果的基础上来计算当前结果。这类题目往往看起来复杂，但是推导出动态规划方程后，问题就迎刃而解了。