This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #1048 (Medium): Longest String Chain
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given a list of
words, each word consists of English lowercase letters.Let's say
word1is a predecessor ofword2if and only if we can add exactly one letter anywhere inword1to make it equal toword2. For example,"abc"is a predecessor of"abac".A word chain is a sequence of words
[word_1, word_2, ..., word_k]withk >= 1, whereword_1is a predecessor ofword_2,word_2is a predecessor ofword_3, and so on.Return the longest possible length of a 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 chain is "a","ba","bda","bdca".
Example 2: Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"] Output: 5
Constraints:
1 <= words.length <= 10001 <= words[i].length <= 16words[i]only consists of English lowercase letters.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
A naive approach would be to check every word against every other word looking for predecessors, but that would lead to a TLE result. The first important realization that we should be able to make is that while a word may have many 26 * (word.length + 1) possible successors, it can only have word.length predecessors.
So rather than iterating from small to large words and checking every combination for a link, we can store the words in a set and only check the few possible predecessors while iterating from large to small. To aid in that, we can actually separate words into an array of sets (W) indexed by word length, so that we can directly access batches of words by their length.
(Note: As we iterate backward through W, if we find that W[i-1] is empty, we don't need to process the words in W[i], since there cannot possibly be a predecessor match.)
Then we can use a dynamic programming (DP) approach to eliminate some common subproblems. We can define a hashmap (dp) where dp[word] is the length of the longest chain ending at word found so far.
So at each word, we'll iterate through each of its predecessors (pred) and check the appropriate set in W for a match. If we find a match, we can update dp[pred] if dp[word] + 1 is better, increasing the chain by one. We should also separately keep track of the best chain length we've seen, so that once we reach the end, we can just return best.
- Time Complexity: O(N*M) where N is the length of words and M is the average length of the words in words.
- Space Complexity: O(N + P) where P is the number of predecessors found and stored in dp.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var longestStrChain = function(words) {
let W = Array.from({length: 17}, _ => new Set())
for (let i = 0; i < words.length; i++)
W[words[i].length].add(words[i])
let dp = new Map(), best = 1
for (let i = 16; i; i--) {
if (!W[i-1].size) continue
for (let word of W[i]) {
let wVal = dp.get(word) || 1
for (let j = 0; j < word.length; j++) {
let pred = word.slice(0,j) + word.slice(j+1)
if (W[i-1].has(pred) && wVal >= (dp.get(pred) || 1)) {
dp.set(pred, wVal + 1)
best = Math.max(best, wVal + 1)
}
}
}
}
return best
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def longestStrChain(self, words: List[str]) -> int:
W = [set() for _ in range(17)]
for word in words:
W[len(word)].add(word)
dp, best = defaultdict(lambda:1), 1
for i in range(16,0,-1):
if len(W[i-1]) == 0: continue
for word in W[i]:
wVal = dp[word]
for j in range(len(word)):
pred = word[0:j] + word[j+1:]
if pred in W[i-1] and wVal >= (dp.get(pred) or 1):
dp[pred] = wVal + 1
best = max(best, wVal + 1)
return best
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public int longestStrChain(String[] words) {
List<Set<String>> W = new ArrayList<>(17);
for (int i = 0; i < 17; i++)
W.add(new HashSet<>());
for (String word : words)
W.get(word.length()).add(word);
Map<String, Integer> dp = new HashMap<>();
int best = 1;
for (int i = 16; i > 0; i--) {
if (W.get(i-1).isEmpty()) continue;
for (String word : W.get(i)) {
int wVal = dp.getOrDefault(word, 1);
for (int j = 0; j < word.length(); j++) {
String pred = word.substring(0,j) + word.substring(j+1);
if (W.get(i-1).contains(pred) && wVal >= dp.getOrDefault(pred,1)) {
dp.put(pred, wVal + 1);
best = Math.max(best, wVal + 1);
}
}
}
}
return best;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
int longestStrChain(vector<string>& words) {
vector<unordered_set<string>> W(17);
for (auto word : words)
W[word.size()].insert(word);
unordered_map<string, int> dp;
int best = 1;
for (int i = 16; i; i--) {
if (W[i-1].empty()) continue;
for (auto word : W[i]) {
int wVal = dp[word] ? dp[word] : 1;
for (int j = 0; j < word.size(); j++) {
string pred = word.substr(0,j) + word.substr(j+1);
int pVal = dp[pred] ? dp[pred] : 1;
if (W[i-1].find(pred) != W[i-1].end() && wVal >= pVal) {
dp[pred] = wVal + 1;
best = max(best, wVal + 1);
}
}
}
}
return best;
}
};
Top comments (0)