> For the complete documentation index, see [llms.txt](https://wentao-shao.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wentao-shao.gitbook.io/leetcode/dynamic-programming/1.position/1048.longest-string-chain.md).

# 1048.Longest-String-Chain

## 1048. Longest String Chain

## 题目地址

<https://leetcode.com/problems/longest-string-chain/>

## 题目描述

```
Given a list of words, each word consists of English lowercase letters.

Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2.  For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a word chain with words chosen from the given list of words.

Example 1:
Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

Note:
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of English lowercase letters.
```

## 代码

### Approach #1 Dynamic Programming

```java
class Solution {
  public int longestStrChain(String[] words) {
        Map<String, Integer> dp = new HashMap<>();
    Arrays.sort(words, (a, b) -> a.length() - b.length());
    int ans = 0;
    for (String word: words) {
      int best = 0;
      for (int i = 0; i < word.length(); i++) {
        String prev = word.substring(0, i) + word.substring(i + 1);
        best = Math.max(best, dp.getOrDefault(prev, 0) + 1);
      }
      dp.put(word, best);
      ans = Math.max(ans, best);
    }

    return ans;
  }
}
```

### Approach #2 DFS

```java
class Solution {
  public int longestStrChain(String[] words) {
    int ans = 0;
    Set<String> set = new HashSet<>();
    Map<String, Integer> map = new HashMap();
    for (String word: words) {
      set.add(word);
    }
    for (String word: words) {
      ans = Math.max(ans, dfs(map, set, word));
    }
    return ans;
  }

  private int dfs(Map<String, Integer> map, Set<String> set, String word) {
    if (map.containsKey(word)) return map.get(word);

    int cnt = 0;
    for (int i = 0; i < word.length(); i++) {
      String next = word.substring(0, i) + word.substring(i + 1);
      if (set.contains(next)) {
        cnt = Math.max(cnt, dfs(map, set, next));
      }
    }

    map.put(word, 1 + cnt);
    return 1 + cnt;
  }
}
```