You are given an array of words where each word consists of lowercase English letters.
wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB.
"abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.
Return the length of the longest possible word chain with words chosen from the given list of words.
Example 1:
Input: words = ["a","b","ba","bca","bda","bdca"] Output: 4 Explanation: One of the longest word chains is ["a","ba","bda","bdca"].
Example 2:
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"] Output: 5 Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].
Example 3:
Input: words = ["abcd","dbqca"] Output: 1 Explanation: The trivial word chain ["abcd"] is one of the longest word chains. ["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.
Constraints:
1 <= words.length <= 10001 <= words[i].length <= 16words[i] only consists of lowercase English letters.This approach involves sorting the array of words based on their lengths, which helps in easily recognizing the potential predecessors. Then, utilize a dynamic programming technique to build up the solution. For each word, check all words that are predecessors and update the maximum chain length accordingly.
The solution is implemented in C using dynamic programming. First, it sorts the array of words according to their lengths. Then, for each word, it checks all previously encountered words to see if they can form a predecessor-successor pair. The dynamic programming array (dp) keeps track of the maximum chain length for each word. The final result is the maximum value in this array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 * l), where n is the number of words and l is the average length of each word. The sorting step contributes O(n log n) but checking each predecessor might happen in O(n^2). The maximum comparison takes O(l) time.
Space Complexity: O(n) for the dp array.
This approach models the words as nodes in a graph and links words via edges if one is a predecessor of the other. The goal is to find the longest path in this directed acyclic graph (DAG), which represents the longest word chain.
This C solution approaches the problem by leveraging the concept of words as nodes in a directed graph. It calculates the longest path in this graph by identifying predecessors.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2 * l), where n is the number of words and l is the average word length as this is similar to a dynamic programming solution.
Space Complexity: O(n) for the dynamic programming path length array.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Sorting | Time Complexity: O(n^2 * l), where n is the number of words and l is the average length of each word. The sorting step contributes O(n log n) but checking each predecessor might happen in O(n^2). The maximum comparison takes O(l) time. |
| Graph-Based Approach | Time Complexity: O(n^2 * l), where n is the number of words and l is the average word length as this is similar to a dynamic programming solution. |
DP 45. Longest String Chain | Longest Increasing Subsequence | LIS • take U forward • 124,366 views views
Watch 9 more video solutions →Practice Longest String Chain with our built-in code editor and test cases.
Practice on FleetCode