Problem
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
.
Examples
Example 1:
Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: One of the longest word chains is ["a","ba","bda","bdca"].
Example 2:
Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5
Explanation: All the words can be put in a word chain ["xb", "xbc", "cxbc", "pcxbc", "pcxbcf"].
Example 3:
Input: words = ["abcd","dbqca"]
Output: 1
Explanation: The trivial word chain ["abcd"] is one of the longest word chains.
["abcd","dbqca"] is not a valid word chain because the ordering of the letters is changed.
Solution
Method 1 - DP
- Sort the
words
by word’s length. (also can apply bucket sort) - For each word, generate all possible previous word
prev
with 1 letter missing. - If we have seen this previous word, update the longest chain for the current word.
- Finally return the longest word chain.
Here is the approach:
- Sorting: Sort the words by their lengths. This ensures that when we try to build the word chain, we only look at words with lengths less than the current word.
- Dynamic Programming: Use a hashmap to keep track of the longest chain ending at each word.
- Checking Predecessors: For each word, try to remove each character one by one to see if the resulting word exists in the hashmap, indicating a valid predecessor.
Code
Java
class Solution {
public int longestStrChain(String[] words) {
Arrays.sort(words, (a, b) -> a.length() - b.length());
Map<String, Integer> dp = new HashMap<>();
int ans = 0;
for (String word : words) {
int maxLen = 0;
for (int i = 0; i < word.length(); i++) {
String predecessor = word.substring(0, i) + word.substring(i + 1);
maxLen = Math.max(maxLen, dp.getOrDefault(predecessor, 0) + 1);
}
dp.put(word, maxLen);
ans = Math.max(ans, maxLen);
}
return ans;
}
}
Python
class Solution:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=len)
dp = {}
ans = 0
for word in words:
max_len = 0
for i in range(len(word)):
predecessor = word[:i] + word[i+1:]
max_len = max(max_len, dp.get(predecessor, 0) + 1)
dp[word] = max_len
ans = max(ans, max_len)
return ans
Complexity
- ⏰ Time complexity:
O(n * m^2)
, wheren
is the number of words, andm
is the maximum length of a word. The sorting takesO(n log n)
. For each word, we potentially look atm
predecessor candidates, each takingO(m)
to check. - 🧺 Space complexity:
O(n)
, used by the hashmap to store the longest chain lengths of words.