---
# System prepended metadata

title: 1048. Longest String Chain
tags: [Leetcode, Medium]

---

# 1048. Longest String Chain
###### tags: `Leetcode` `Medium`
## 思路
相比于每次加一个字符，可以反过来看每次减一个字符
先按照长度把所有字符排序
拿到任何一个字符串之后，把每个位置的字母都尝试删掉一遍，如果删掉之后这个字母的字符串有没有在words里面，更新现在的结果
## Code
```java=
class Solution {
    public int longestStrChain(String[] words) {
        Arrays.sort(words, (a,b)->(a.length()-b.length()));
        Map<String, Integer> dp = new HashMap<>();
        int ans = 1;
        for(String word:words){
            dp.put(word, 1);
            for(int i=0; i<word.length(); i++){
                String tmp = word.substring(0,i)+word.substring(i+1);
                if(dp.containsKey(tmp) && dp.get(tmp)+1>dp.get(word)){
                    dp.put(word, dp.get(tmp)+1);
                }
            }
            ans = Math.max(ans, dp.get(word));
        }
        return ans;
    }
}
```