1048.最长字符串链子（个人感觉解法很棒）

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# author：ShidongDu time:2020/2/11
'''
给出一个单词列表，其中每个单词都由小写英文字母组成。

如果我们可以在 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] 仅由小写英文字母组成。
'''

'''
题解：
思路

动态规划

word1在任意位置添加一个字母变成word2”等价于“word2在任意一个位置减去一个字母变成word1”（假设叫做逆前身），
则word中最长的词链就是[word_1,word_2,...,word_k]组成的序列，其中word_3是word_2的逆前身，word_2是word_1的逆前身，以此类推；
假设有一个笔记本note，记录words中所有单词的词链长度chain，则对于word，他的最长词链长度为chain = max(1,1+note[subWord])，
其中subWord表示的是word的每一个逆前身，且这个逆前身在words中（也就是说note中有subWord的记录）；
对于words按照word的长度进行排序，排序后逐个对word按照步骤2的公式进行判断。如果word在note中没有记录，
则说明word没有逆前身，他的chain为1.

举例:
words=["a","b","ba","bca","bda","bdca"]

初始化note={}
对于a，note中无记录，则chain为1，note={"a":1}
对于b，同上，note={"a":1,"b":1}
对于ba，chain=max(1,1+note[b],1+note[a])=2,note={"a":1,"b":1,"ba"=2}
对于bca，chain=max(1,1+note[ba])=3,note={"a":1,"b":1,"ba"=2,"bca":3}
对于bda，同上，note={"a":1,"b":1,"ba"=2,"bca":3,"bda":3}
对于bdca，chain=max(1,1+note[bca],1+note[bda])=4
遍历所有word之后，可知最大词链长度为4

'''
from typing import List
class Solution:
    def longestStrainChain(self, words: List[str]) -> int:
        words.sort(key=len)
        note = {}
        for word in words:
            if word not in note:
                note[word] = 1  # 如果第一次遇到，置一
            # 接下来
            for j in range(len(word)):
                new_word = word[: j]+ word[j+1:]
                if new_word in note:
                    note[word] = max(note[word], note[new_word]+1)

        return max(note.values())

solution = Solution()
res = solution.longestStrainChain(["a","b","ba","bca","bda","bdca"])
print(res)