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 <iostream>
2#include <vector>
3#include <algorithm>
4#include <unordered_map>
5
6using namespace std;
7
8bool isPredecessor(const string &a, const string &b) {
9 if (b.length() != a.length() + 1) return false;
10 int i = 0, j = 0;
11 while (j < b.length()) {
12 if (i < a.length() && a[i] == b[j]) {
13 i++;
14 }
15 j++;
16 }
17 return i == a.length();
18}
19
20int longestStrChain(vector<string> &words) {
21 sort(words.begin(), words.end(), [](string &a, string &b) {
22 return a.length() < b.length();
23 });
24
25 unordered_map<string, int> dp;
26 int maxLen = 1;
27
28 for (const string &word : words) {
29 dp[word] = 1;
30 for (int i = 0; i < word.length(); i++) {
31 string prev = word.substr(0, i) + word.substr(i + 1);
32 if (dp.find(prev) != dp.end()) {
33 dp[word] = max(dp[word], dp[prev] + 1);
34 }
35 }
36 maxLen = max(maxLen, dp[word]);
37 }
38
39 return maxLen;
40}
41
42int main() {
43 vector<string> words = {"a", "b", "ba", "bca", "bda", "bdca"};
44 cout << longestStrChain(words) << endl;
45 return 0;
46}This solution implements a similar dynamic programming approach in C++. The words are sorted by length, and for each word, it checks leaving one letter at a time to find its predecessor in the hashmap. The dynamic programming stores the maximum chain length in the hashmap dp for each word.
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.