1048. Longest String Chain

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.

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](const string& s1, const string& s2){return s1.length() < s2.length(); });
        unordered_map<string, int> dp;
        for(auto& s : words) {
            string str = s.substr(1);
            dp[s] = max(dp[s], dp.find(str) == dp.end() ? 1 : dp[str] + 1);
            for(int i = 0; i < s.length() - 1; i++) {
                str[i] = s[i];
                dp[s] = max(dp[s], dp.find(str) == dp.end() ? 1 : dp[str] + 1);
            }
        }
        return max_element(dp.begin(), dp.end(), [](const auto& e1, const auto& e2) {return e1.second < e2.second; })->second;
    }
};