给出一个单词数组 words ，其中每个单词都由小写英文字母组成。
如果我们可以 不改变其他字符的顺序 ，在 wordA 的任何地方添加 恰好一个 字母使其变成 wordB ，那么我们认为 wordA 是 wordB 的 前身 。
例如，"abc" 是 "abac" 的 前身 ，而 "cba" 不是 "bcad" 的 前身
词链是单词 [word_1, word_2, ..., word_k] 组成的序列，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] 仅由小写英文字母组成。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-string-chain
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
最近咋感觉都是动规题。
由于符合要求的两个字符串 s1 和 s2 ，两者的长度差一定为 1 。
则可以想到，以 s2 为结尾的最长字符串链，一定是以 s1 为结尾的最长字符串链的长度加一。
class Solution { public int longestStrChain (String[] words) { int res = 0; Arrays.sort(words, (a, b) -> (a.length() - b.length())); int[] dp = new int[words.length]; for (int i = 0; i < words.length; i++) { for (int j = 0; j < i; j++) { if (judge(words[j], words[i])) { dp[i] = Math.max(dp[i], dp[j] + 1); } } res = Math.max(res, dp[i]); } return res + 1; } private boolean judge (String str1, String str2) { int len1 = str1.length(); int len2 = str2.length(); if (len1 + 1 != len2) { return false; } int i = 0; int j = 0; while (i < len1 && j < len2) { while (j < len2 && str2.charAt(j) != str1.charAt(i)) { j++; } i++; j++; } return i == str1.length() && j <= len2; } }
