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.
Solution:
DFS + memo
class Solution {
public int longestStrChain(String[] words) {
Set<String> set = new HashSet();
for (String w : words) {
set.add(w);
}
int max = 1;
Map<String, Integer> map = new HashMap();
for (String w : words) {
set.remove(w);
max = Math.max(max, 1 + dfs(w, set, map));
set.add(w);
}
return max;
}
private int dfs(String w, Set<String> set, Map<String, Integer> map) {
if (map.containsKey(w)) {
return map.get(w);
}
int max = 0;
for (int i = 0; i <= w.length(); i ++) {
for (char c = 'a'; c <= 'z'; c ++) {
String str = w.substring(0, i) + String.valueOf(c) + w.substring(i, w.length());
if (set.contains(str)) {
set.remove(str);
max = Math.max(max, 1 + dfs(str, set, map));
set.add(str);
}
}
}
map.put(w, max);
return max;
}
}
dp:
Sort the words by word's length. (also can apply bucket sort) For each word, loop on all possible previous word with 1 letter missing. If we have seen this previous word, update the longest chain for the current word. Finally return the longest word chain.
class Solution {
public int longestStrChain(String[] words) {
Map<String, Integer> dp = new HashMap<>();
Arrays.sort(words, (a, b) -> a.length() - b.length());
int res = 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);
res = Math.max(res, best);
}
return res;
}
}