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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <stdbool.h>
5
6int cmp(const void *a, const void *b) {
7 return strlen(*(const char **)a) - strlen(*(const char **)b);
8}
9
10bool isPredecessor(char *a, char *b) {
11 if (strlen(b) != strlen(a) + 1) return false;
12 int i = 0, j = 0;
13 while (j < strlen(b)) {
14 if (i < strlen(a) && a[i] == b[j]) {
15 i++;
16 }
17 j++;
18 }
19 return i == strlen(a);
20}
21
22int longestStrChain(char **words, int wordsSize) {
23 int *dp = (int *)malloc(sizeof(int) * wordsSize);
24 memset(dp, 1, sizeof(int) * wordsSize);
25
26 qsort(words, wordsSize, sizeof(char *), cmp);
27
28 int maxLen = 1;
29 for (int i = 0; i < wordsSize; i++) {
30 for (int j = 0; j < i; j++) {
31 if (isPredecessor(words[j], words[i]) && dp[i] < dp[j] + 1) {
32 dp[i] = dp[j] + 1;
33 }
34 }
35 if (maxLen < dp[i]) {
36 maxLen = dp[i];
37 }
38 }
39
40 free(dp);
41 return maxLen;
42}
43
44int main() {
45 char *words[] = {"a", "b", "ba", "bca", "bda", "bdca"};
46 int wordsSize = sizeof(words) / sizeof(words[0]);
47 printf("%d\n", longestStrChain(words, wordsSize));
48 return 0;
49}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.
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 JavaScript solution utilizes a graph-based approach where edges signify precedence among vertices, and the algorithm boils down to identifying the longest path within this graph structure.