Leetcode 1048: Longest String Chain
You are given an array of words, where each word consists of lowercase English letters. A wordA is considered a predecessor of wordB if you can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to wordB. A word chain is a sequence of words such that each word is a predecessor of the next one. Your task is to find the length of the longest word chain that can be formed from the given list of words.
Problem
Approach
Steps
Complexity
Input: You are given an array of words, each consisting of lowercase English letters.
Example: Input: words = ["a", "ab", "abc", "abcd"]
Constraints:
• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] only consists of lowercase English letters.
Output: Return the length of the longest possible word chain that can be formed from the list of words.
Example: Output: 4
Constraints:
• The answer will always be a positive integer.
Goal: The goal is to compute the longest word chain by checking if a word can be a predecessor of another.
Steps:
• 1. Sort the words based on their lengths.
• 2. Use dynamic programming to track the longest chain ending at each word.
• 3. For each word, try to form a predecessor by removing one character at a time and check if the resulting word exists in the previous words of the list.
• 4. The result is the maximum length of all possible word chains.
Goal: You are guaranteed that the number of words is at most 1000, and each word has a length of at most 16 characters.
Steps:
• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
Assumptions:
• Each word consists of lowercase English letters only.
• The words are provided in an array, and their lengths vary.
• Input: Input: words = ["a", "ab", "abc", "abcd"]
• Explanation: In this example, we can form the word chain ["a", "ab", "abc", "abcd"]. Each word is a predecessor of the next, resulting in a chain length of 4.
• Input: Input: words = ["xbc", "pcxbcf", "xb", "cxbc", "pcxbc"]
• Explanation: In this example, all words can be arranged into the word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"], resulting in a chain length of 5.
Approach: To solve the problem efficiently, we can use dynamic programming and sorting to form the longest word chain.
Observations:
• The problem involves finding the longest sequence of words where each word can be transformed into the next by adding one character.
• Sorting the words by length allows us to progressively check possible predecessors for each word.
• A dynamic programming approach is well-suited to track the longest chain ending at each word.
Steps:
• 1. Sort the words based on their lengths.
• 2. Use a map to store the longest chain length for each word.
• 3. For each word, iterate through all possible predecessors by removing one character at a time.
• 4. Update the longest chain length for the current word based on its predecessors.
• 5. Return the maximum length from the map.
Empty Inputs:
• If there are no words, the longest word chain length is 0.
Large Inputs:
• For large inputs, the algorithm will efficiently compute the longest word chain due to the dynamic programming approach.
Special Values:
• If all words are of the same length, no word can be a predecessor of another, and the longest chain length is 1.
Constraints:
• The number of words is guaranteed to be at most 1000, and each word has a length of at most 16 characters.
static bool cmp(string &a, string &b) {
return a.size() < b.size();
}
int longestStrChain(vector<string>& words) {
sort(words.begin(), words.end(), cmp);
map<string, int> dp;
int mx = 1;
for(int i = 0; i < words.size(); i++) {
string w = words[i];
for(int j = 0; j < w.size(); j++) {
string w1 = w.substr(0, j) + w.substr(j + 1);
dp[w] = max(dp[w], dp.count(w1)? dp[w1] + 1: 1);
}
mx = max(mx, dp[w]);
}
return mx;
}
1 : Function Definition
static bool cmp(string &a, string &b) {
Define a static comparison function 'cmp' that compares the size of two strings. This function is used for sorting the words in increasing order of their lengths.
2 : Comparison Logic
return a.size() < b.size();
Return true if the size of string 'a' is smaller than that of string 'b', otherwise return false. This is used to sort the words in ascending order of their lengths.
3 : Function Definition
int longestStrChain(vector<string>& words) {
Define the function 'longestStrChain' which takes a vector of strings 'words' and returns the length of the longest string chain.
4 : Sorting
sort(words.begin(), words.end(), cmp);
Sort the 'words' vector in increasing order of word length using the comparison function 'cmp'.
5 : Variable Declaration
map<string, int> dp;
Declare a map 'dp' where each key is a word, and the value is the length of the longest chain ending with that word.
6 : Variable Initialization
int mx = 1;
Initialize 'mx' to 1, which will store the length of the longest string chain found so far.
7 : Loop Through Words
for(int i = 0; i < words.size(); i++) {
Start a for loop that iterates through each word in the sorted 'words' vector.
8 : Assign Word
string w = words[i];
Assign the current word in the iteration to the variable 'w'.
9 : Loop Through Word Characters
for(int j = 0; j < w.size(); j++) {
Start an inner loop that iterates through each character of the current word 'w'.
10 : Create Substring
string w1 = w.substr(0, j) + w.substr(j + 1);
Create a new string 'w1' by removing the character at index 'j' from the string 'w'. This helps in checking if the current word can form a chain with a previous word.
11 : Update DP Map
dp[w] = max(dp[w], dp.count(w1)? dp[w1] + 1: 1);
Update the value of 'dp[w]' by checking if a smaller word 'w1' exists in the map 'dp'. If it does, the chain length is increased by 1. Otherwise, it starts a new chain with length 1.
12 : Update Maximum Chain Length
mx = max(mx, dp[w]);
Update the maximum chain length 'mx' by comparing it with the current chain length stored in 'dp[w]'.
13 : Return Result
return mx;
Return the value of 'mx', which is the length of the longest string chain.
Best Case: O(n log n)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: In the worst case, we check all possible predecessors for each word, leading to a time complexity of O(n^2) where n is the number of words.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space required to store the map of longest chain lengths.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus