难度：★★★☆☆
类型：字符串
方法：动态规划
题目
力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录
给出一个单词列表，其中每个单词都由小写英文字母组成。
如果我们可以在 word1 的任何地方添加一个字母使其变成 word2，那么我们认为 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。
词链是单词 [word_1, word_2, ..., word_k] 组成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此类推。
从给定单词列表 words 中选择单词组成词链，返回词链的最长可能长度。
示例：
输入：["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 "a","ba","bda","bdca"。
提示：
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] 仅由小写英文字母组成。
解答
单词是以集合的形式给出的，这也就意味着，是无序的，这是这道题目需要注意的一点。
我们使单词按照长度从短到长排序，便于动态规划的遍历统计。
【数组定义】
定义字典dp，字典中的键代表每个单词word，字典的值代表以单词word结尾的链的最大长度。
【初始状态】
将每个单词对应的数值填充为零。
【递推公式】
从短到长遍历每个单词word，研究该单词分别去掉其中一个字符后形成的单词word_strip，查看它是否在单词列表中出现过，若该单词出现在列表中，则说明可以将word_strip结尾的链增加一个word延长一个长度，dp[word_strip] + 1（当然需要和当前值dp[word]进行比较，选更大的），如果word去掉每个位置处的字母得到的新单词都没有出现在单词列表words中，则dp[word]设置为1。
【返回值】
最终返回dp字典的值列表中的最大值即可。
from typing import List
from collections import defaultdict
class Solution:
def longestStrChain(self, words: List[str]) -> int:
dp = defaultdict(int)
words.sort(key=len)
for word in words:
for i in range(len(word)):
word_strip = word[:i] + word[i + 1:]
dp[word] = max(dp[word], dp[word_strip] + 1)
return max(dp.values())
扩展：如果有顺序要求呢
如果单词不是以集合的形式给出，而是以列表的形式给出，也就是说需要保证有序，那么这道题就转换成了类似300.求最长递增子序列的问题。也是要用动态规划。换了一个马夹而已，请看原来题目的解法：
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
dp = [1 for _ in range(n)]
for i in range(n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i],dp[j] + 1)
return max(dp)
对于这道题，重新增加一个函数用来比较单词之间能否建立连接就好了。
class Solution:
def longestStrChain(self, words: List[str]) -> int:
if not words:
return 0
n = len(words)
dp = [1 for _ in range(n)]
words.sort(key=len) # 如果要求顺序，则不需要这句话
for i in range(n):
for j in range(i):
if self.cmp(words[j], words[i]):
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
@staticmethod
def cmp(w1, w2):
if len(w1) + 1 != len(w2):
return False
w1, w2 = list(w1), list(w2)
while w1 and w1[0] == w2[0]:
w1.pop(0)
w2.pop(0)
w2.pop(0)
while w1 and w1[0] == w2[0]:
w1.pop(0)
w2.pop(0)
if w1 == w2 == []:
return True
return False
这里可以通过 words.sort(key=len) 这句话的有无来控制题目是否要求有序。读者把这段代码粘贴过去也是可以运行的。
如有疑问或建议，欢迎评论区留言~
有关更多力扣中等题的python解决方案，请移步力扣中等题解析
