seanpgallivan

Posted on

Solution: Longest String Chain

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.

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 `word1` is a predecessor of `word2` if and only if we can add exactly one letter anywhere in `word1` to make it equal to `word2`. For example, `"abc"` is a predecessor of `"abac"`.

A word chain is a sequence of words `[word_1, word_2, ..., word_k]` with `k >= 1`, where `word_1` is a predecessor of `word_2`, `word_2` is a predecessor of `word_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 <= 1000`
• `1 <= words[i].length <= 16`
• `words[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:

``````var longestStrChain = function(words) {
let W = Array.from({length: 17}, _ => new Set())
for (let i = 0; i < words.length; 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:

``````class Solution:
def longestStrChain(self, words: List[str]) -> int:
W = [set() for _ in range(17)]
for word in words:
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:

``````class Solution {
public int longestStrChain(String[] words) {
List<Set<String>> W = new ArrayList<>(17);
for (int i = 0; i < 17; i++)
for (String word : words)
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:

``````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;
}
};
``````