LeetCode [1048] Longest String Chain

1048. Longest String Chain

Medium

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. 1 <= words.length <= 1000
2. 1 <= words[i].length <= 16
3. words[i] only consists of English lowercase letters.

class Solution {
    public int longestStrChain(String[] words) {
        int ret = 0;
        Arrays.sort(words, Comparator.comparingInt(String::length));   
        Map<String, Integer> dp = new HashMap<>();
        for(String w : words){
            if(dp.containsKey(w)) continue;
            int best = 0;
            for(int i=0; i<w.length(); ++i){
                String prev = w.substring(0, i) + w.substring(i+1);//remove i-th char
                best = Math.max(best, dp.getOrDefault(prev, 0)+1);
            }
            dp.put(w, best);
            ret = Math.max(ret, best);
        }
        return ret;
    }
}