# 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;
  }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wentao-shao.gitbook.io/leetcode/dynamic-programming/1.position/1048.longest-string-chain.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.