Sponsored
Sponsored
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.
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.
1import java.util.*;
2
3public class Solution {
4 public int longestStrChain(String[] words) {
5 Arrays.sort(words, Comparator.comparingInt(String::length));
6 Map<String, Integer> dp = new HashMap<>();
7 int maxLen = 1;
8
9 for (String word : words) {
10 dp.put(word, 1);
11 for (int i = 0; i < word.length(); i++) {
12 String prev = word.substring(0, i) + word.substring(i + 1);
13 if (dp.containsKey(prev)) {
14 dp.put(word, Math.max(dp.get(word), dp.get(prev) + 1));
15 }
16 }
17 maxLen = Math.max(maxLen, dp.get(word));
18 }
19
20 return maxLen;
21 }
22
23 public static void main(String[] args) {
24 Solution solution = new Solution();
25 String[] words = {"a", "b", "ba", "bca", "bda", "bdca"};
26 System.out.println(solution.longestStrChain(words));
27 }
28}This Java solution uses sorting and a HashMap to track maximum chain lengths. For each word, it looks for possible predecessors by removing each letter one at a time. If a predecessor is found in the map, it updates the chain length accordingly.
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.
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.
1
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.