@(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 <= words.length <= 10001 <= words[i].length <= 16word[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;
}
总结一下，这道题属于动态规划类，即在前面结果的基础上来计算当前结果。这类题目往往看起来复杂，但是推导出动态规划方程后，问题就迎刃而解了。
