力扣---1048. 最长字符串链

给出一个单词数组 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;
    }
}