1048. Longest String Chain

Description

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.

Constraints

• 1 <= words.length <= 1000

• 1 <= words[i].length <= 16

• words[i] only consists of English lowercase letters.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: words = ["a", "b", "ba", "bca", "bda", "bdca"]

Output: 4

Explanation: One of the longest word chain is "a", "ba", "bda", "bdca".

Example 2

Input: words = ["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]

Output: 5

Solutions

Solution 1

/**
 * Time complexity : O(N *(log(N+L^2))). Where N be the number of words in 
 *    the list and L be the maximum possible length of a word.
 * Space complexity : O(N). We use a map to store the length of the longest 
 *    sequence formed with each of the NN words as the end word.
 */

class Solution {
    public int longestStrChain(String[] words) {
        if(words == null || words.length < 2) {
            return words == null? 0: words.length;
        }
        Arrays.sort(words, (a, b) -> a.length()-b.length());
        Map<String, Integer> map = new HashMap();
        int longest = 0;

        for(String word: words) {
            int currLongest = 0;
            for(int i = 0; i < word.length(); i++) {
                StringBuilder prevWordSb = new StringBuilder(word);
                prevWordSb.deleteCharAt(i);
                int prevLength = 1 + map.getOrDefault(prevWordSb.toString(), 0);
                currLongest = Math.max(currLongest, prevLength);
            }
            map.put(word, currLongest);
            longest = Math.max(longest, currLongest);
        }

        return longest;
    }
}

Follow up