1048. 最长字符串链

原题地址：https://leetcode.cn/problems/longest-string-chain/

题解

参考官方题解

设dp[i]为words[i]能够组成的最长词链长度，考虑到其前身必然为恰好只比words[i]少一个字符的词，我们可以先将words数组从小到大排序

//这里用了一个lambda表达式来传入排序规则comparator
Arrays.sort(words,(String a,String b)->{
    return a.length()-b.length();
});

在排完序后，我们就可以在处理完所有能够满足words[i]前身要求的所有词后，再去处理words[i]

对于任何满足其前身要求的words[j]，其与words[i]组成的词链长度为dp[j]+1，于是我们有：

考虑到从words中寻找words[i]的前身并不容易，我们可以通过哈希表的形式来实现dp数组，对于任意j遍历[0,words[i].length()-1]，如果哈希表中存在键**words[i].substring(0,j)+words[i].substring(j+1,words[i].length())**（即只缺少第j个字符）的话，则说明words中含有该词，由于我们事先已经对数组排过序，因此不用担心漏掉情况

与此同时用一个max变量，每次遍历更新dp[i]时就与其比较，最后输出max即可

时间复杂度：O(NlogN+N^2)

空间复杂度：O(N)

class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words,(String a,String b)->{
            return a.length()-b.length();
        });

        Map<String,Integer> map=new HashMap<>();
        String prev;
        int max=1;
        for (int i=0;i< words.length;i++){
            map.put(words[i],1);
            for(int j=0;j<words[i].length();j++){
                prev=words[i].substring(0,j)+words[i].substring(j+1,words[i].length());
                if(map.containsKey(prev)){
                    map.put(words[i],Math.max(map.get(words[i]),map.get(prev)+1));
                }
            }
            max=Math.max(max,map.get(words[i]));
        }

        return max;
    }
}