[LC] 1048. 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".

class Solution {

    public int longestStrChain(String[] words) {

        Arrays.sort(words, (a, b) -> a.length() - b.length());

        // map is used as space for dp best[i] = 1 + best[i- 1]

        Map<String, Integer> map = new HashMap<>();

        int res = 0;

        for (String word: words) {

            map.put(word, 1);

            for (int i = 0; i < word.length(); i++) {

                String prev = word.substring(0, i) + word.substring(i + 1);

                int curLen = map.get(word);

                if (map.containsKey(prev) && map.get(prev) + 1 > curLen) {

                    map.put(word, map.get(prev) + 1);

                }

            }

            res = Math.max(res, map.get(word));

        }

        return res;

    }

}

巴特西

[LC] 1048. Longest String Chain

最新文章

热门文章