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.

Example 1:

Input: ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: one of the longest word chain is "a","ba","bda","bdca".

Note:

1. 1 <= words.length <= 1000
2. 1 <= words[i].length <= 16
3. words[i] only consists of English lowercase letters.

struct comp {

    bool operator()(string& a, string& b) {

        return a.size() < b.size();

    }

};

class Solution {

private:

    bool predecessor(string& next, string& str) {

        if (next.size() != str.size() + 1) {

            return false;

        }

        map<char, int> mp;

        for (auto ch : str) {

            mp[ch]++;

        }

        

        int diff_count = 0;

        for (auto ch : next) {

            if (!mp.count(ch) || mp[ch] < 0) {

                diff_count++;

                if (diff_count > 1) {

                    return false;

                }

            } else {

                if (--mp[ch] == 0) {

                    mp.erase(ch);

                };

            }

        }

        return diff_count == 1 && mp.size() == 0;

    }

    

public:

    int longestStrChain(vector<string>& words) {

        int ans = 1;

        sort(words.begin(), words.end(), comp());

        helper(words, ans);

        return ans;

    }

    

    void helper(vector<string>& words, int& ans) {

        vector<int> temp(words.size(), 1);

        for (int i = 1; i < words.size(); i++) {

            for (int j = i - 1; j >= 0; j--) {

                if (predecessor(words[i], words[j])) {

                    temp[i] = max(temp[i], temp[j] + 1);

                    ans = max(ans, temp[i]);

                }

            }

        }

    }

};

========= Efficient one =======

class Solution { public: int longestStrChain(vector<string>& words) { int N = words.size(); sort(words.begin(), words.end(), [](const string& a, const string& b) { return a.size() < b.size(); }); unordered_map<string, int> dp; int maxi = 1; for (int i = 0; i < N; ++i) { dp[words[i]] = 1; for (int j = 0; j < words[i].size(); ++j) { string t = words[i]; t.erase(t.begin()+j); if (dp.count(t)) dp[words[i]] = max(dp[words[i]], dp[t]+1); } maxi = max(maxi, dp[words[i]]); } return maxi; } };