1048. Longest String Chain
You are given an array of words
where each word consists of
lowercase English letters.
wordA
{" "}
is a predecessor of{" "}
wordB
{" "}
if and only if we can insert exactly one letter anywhere in{" "}
wordA
{" "}
without changing the order of the other characters to make
it equal to{" "}
wordB
.
-
For example,
"abc"
is a predecessor of{" "}"abac"
, while"cba"
is not a predecessor of{" "}"bcad"
.
A word chain
is a sequence of words{" "}
[word1, word2, ..., wordk]
{" "}
with k >= 1
, where{" "}
word1
{" "}
is a predecessor of{" "}
word2
,{" "}
word2
{" "}
is a predecessor of{" "}
word3
, and so on. A single word is trivially a word chain with{" "}
k == 1
.
Return{" "}
the length of the{" "}
longest possible word chain with words chosen from the
given list of{" "}
words
.
Example 1:
Input: words = ["a","b","ba","bca","bda","bdca"]{"\n"} Output: 4{"\n"} Explanation: One of the longest word chains is ["a"," ba","bda","bdca"].{"\n"}
Example 2:
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]{"\n"} Output: 5{"\n"} Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].{"\n"}
Example 3:
Input: words = ["abcd","dbqca"]{"\n"} Output: 1{"\n"} Explanation: The trivial word chain ["abcd"] is one of the longest word chains.{"\n"}["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.{"\n"}
Constraints:
-
1 <= words.length <= 1000
-
1 <= words[i].length <= 16
-
words[i]
only consists of lowercase English letters.
Solution
Naive Solutions
We could go through all possible chains and check if each works, or we could use a recursive function that adds one character every time, but these solutions are too slow.
Dynamic Programming Solution
Let's build a chain from the shortest string to the longest string. Say we currently have the chain . We see that it doesn't matter what any of the words before are, only that there are of them. This suggests a dynamic programming solution, where the length of the longest chain that ends with the string .
First sort by increasing length. An outer loop will loop . For each , we have an inner loop to check every word before it to see if it can be a predecessor. We'll call this index . If so, we update to because we can extend the chain ending in by appending .
For example, when , , and , we find that removing from yields .
Time complexity
Let and .
Sorting takes .
Our nested loops take and call isPredecessor()
that runs in , so this part takes .
The total time complexity of this algorithm is therefore .
Space complexity
The array consumes memory.
Solutions below
C++ Solution
class Solution {
public:
bool isPredecessor(string &previous_word, string ¤t_word) {
if (previous_word.size() + 1 == current_word.size()) {
for (int k = 0; k < current_word.size(); k++) {
if (previous_word == current_word.substr(0, k) + current_word.substr(k + 1))
return true;
}
}
return false;
}
int longestStrChain(vector<string> &words) {
// sort words by length
sort(words.begin(), words.end(), [](auto x, auto y) { return x.size() < y.size(); });
int n = words.size();
vector<int> dp(n, 1);
for (int current_word_index = 0; current_word_index < n; current_word_index++) {
for (int previous_word_index = 0; previous_word_index < current_word_index; previous_word_index++) {
if (isPredecessor(words[j], words[current_word_index])) {
dp[current_word_index] = max(dp[current_word_index], dp[previous_word_index] + 1);
}
}
}
return *max_element(dp.begin(), dp.end());
}
};
Java Solution
class Solution {
public static boolean isPredecessor(String previous_word, String current_word) {
if (previous_word.length() + 1 == current_word.length()) {
for (int k = 0; k < current_word.length(); k++) {
if (previous_word.equals(current_word.substring(0, k) + current_word.substring(k+1)))
return true;
}
}
return false;
}
public int longestStrChain(String[] words) {
// sort words by length
Arrays.sort(words, (a, b) -> Integer.compare(a.length(), b.length()));
int n = words.length;
// add padding to words to avoid index out of bounds errors
for (int i = 0; i < n; i++) {
words[i] = "#" + words[i];
}
int ans = 1;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int current_word_index = 0; current_word_index < n; current_word_index++) {
for (int previous_word_index = 0; previous_word_index < current_word_index; previous_word_index++) {
if (isPredecessor(words[previous_word_index], words[current_word_index])) {
dp[current_word_index] = Math.max(dp[current_word_index], dp[previous_word_index] + 1);
ans = Math.max(ans, dp[current_word_index]);
}
}
}
return ans;
}
}
Python Solution
class Solution: def isPredecessor(self, previous_word, current_word): if len(previous_word) + 1 == len(current_word): for k in range(len(current_word)): if previous_word == current_word[0:k] + current_word[k+1:]: return True return False def longestStrChain(self, words: List[str]) -> int: words.sort(key=len) n = len(words) dp = [1 for _ in range(n)] for current_word_index in range(n): for previous_word_index in range(current_word_index): if self.isPredecessor(words[previous_word_index], words[current_word_index]): dp[current_word_index] = max(dp[current_word_index], dp[previous_word_index] + 1) return max(dp)
JavaScript Solution
var isPredecessor = function (previous_word, current_word) { if (previous_word.length + 1 == current_word.length) { for (let k = 0; k < current_word.length; k++) { if ( previous_word === current_word.slice(0, k) + current_word.slice(k + 1) ) return true; } } return false; }; /** * @param {string[]} words * @return {number} */ var longestStrChain = function (words) { // sort words by length words.sort((a, b) => a.length - b.length); n = words.length; dp = new Array(n).fill(1); for ( let current_word_index = 0; current_word_index < n; current_word_index++ ) { for ( let previous_word_index = 0; previous_word_index < current_word_index; previous_word_index++ ) { if ( isPredecessor(words[previous_word_index], words[current_word_index]) ) { dp[current_word_index] = Math.max( dp[current_word_index], dp[previous_word_index] + 1 ); } } } return Math.max(...dp); };
Dynamic Programming Solution (requires HashMap)
In our last solution, checking all previous words for predecessors was slow.
Observe that each word can only have predecessors, so we can generate them all (in ) and check the best value we can get from them.
Let the length of the longest chain that ends with the string . will be a hashmap to allow for retrieval by key.
As we did before, sort by increasing length. Loop through the current string . Then for each index , let be with its th character removed. Set to . Our answer is the max of all entries in .
Time complexity
Let and .
Sorting takes .
For every string (there are of them), create each of its predecessors in and check for their value in in . This comes together to .
The total time complexity is therefore .
Space complexity
The hashmap consumes memory.
Bonus:
We can perform counting sort in , giving a total time complexity of .