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.
1using System.Collections.Generic;
public class Solution {
public int LongestStrChain(string[] words) {
Array.Sort(words, (a, b) => a.Length.CompareTo(b.Length));
Dictionary<string, int> dp = new Dictionary<string, int>();
int maxLen = 1;
foreach (string word in words) {
dp[word] = 1;
for (int i = 0; i < word.Length; i++) {
string prev = word.Substring(0, i) + word.Substring(i + 1);
if (dp.ContainsKey(prev)) {
dp[word] = Math.Max(dp[word], dp[prev] + 1);
}
}
maxLen = Math.Max(maxLen, dp[word]);
}
return maxLen;
}
public static void Main(string[] args) {
Solution solution = new Solution();
string[] words = new [] {"a", "b", "ba", "bca", "bda", "bdca"};
Console.WriteLine(solution.LongestStrChain(words));
}
}Graph vertices in this C# solution represent individual words, and directed edges indicate a predecessor relationship. Finding the longest path effectively implies the chain solution.