This question can be solved using a very straightforward dynamic programming approach:
- Sort the words by their lengths: you can either use the
sort()function with a lambda comparator or do bucket sort - Iterate through the list and for each word w, store the maximum length of string chain ending at this word in a map. To find the length chain for w, consider all the words by removing an alphabet from w and check if the new word, w’, exists in the hash map. Programmatically,
dp[w] = max(dp[w], 1+dp[w'])where w’ are all the words derived by removing an alphabet from w.
class Solution {
public:
int longestStrChain(vector<string>& words) {
sort(begin(words), end(words), [](string a, string b) {return a.size()<b.size();});
unordered_map<string, int> dp;
int res = 0;
for (auto s : words) {
for (int i=0; i<s.size(); i++)
dp[s] = max(dp[s], 1+dp[s.substr(0, i) + s.substr(i+1)]);
res = max(res, dp[s]);
}
return res;
}
};
Time complexity: O(n*maxLen(w)). The TC depends on length of w because of the substr() function
Space complexity: O(n)