# 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

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

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) {
}
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;
}
}

Last updated