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#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
bool isPredecessor(const string &a, const string &b) {
if (b.length() != a.length() + 1) return false;
int i = 0, j = 0;
while (j < b.length()) {
if (i < a.length() && a[i] == b[j]) {
i++;
}
j++;
}
return i == a.length();
}
int longestStrChain(vector<string> &words) {
sort(words.begin(), words.end(), [](string &a, string &b) {
return a.length() < b.length();
});
unordered_map<string, int> dp;
int maxLen = 1;
for (const string &word : words) {
dp[word] = 1;
for (int i = 0; i < word.length(); i++) {
string prev = word.substr(0, i) + word.substr(i + 1);
if (dp.find(prev) != dp.end()) {
dp[word] = max(dp[word], dp[prev] + 1);
}
}
maxLen = max(maxLen, dp[word]);
}
return maxLen;
}
int main() {
vector<string> words = {"a", "b", "ba", "bca", "bda", "bdca"};
cout << longestStrChain(words) << endl;
return 0;
}In this C++ solution, each word represents a vertex in a graph, and an edge is drawn if a word is a predecessor of another. The problem reduces to finding the longest path in a directed acyclic graph (DAG).