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.

// Dynamic Programming
int longestStrChain(vector<string>& words) { // time: O(N * log(N) * S); space: O(N * S); N: input size, S: string length
    sort(words.begin(), words.end(), [] (const string& w1, const string& w2) {
        return w1.length() < w2.length();
    });
    unordered_map<string, int> dp;
    int res = 0;
    for (const string& w : words) {
        int curLen = 0;
        for (int i = 0; i < w.length(); ++i) {
            string short_w = w.substr(0, i) + w.substr(i + 1);
            curLen = max(curLen, dp[short_w] + 1);
        }
        dp[w] = curLen;
        res = max(res, curLen);
    }
    return res;
}

int helper(const string& s, unordered_map<string, int>& word_map) {
    int localRes = 1;
    string short_str;
    for (int i = 0; i < s.length(); ++i) {
        short_str = s.substr(0, i) + s.substr(i + 1); // remove s[i]
        if (word_map.count(short_str)) {
            localRes = max(localRes, word_map[short_str] + 1);
        }
    }
    return localRes;
}
int longestStrChain(vector<string>& words) {
    // sort by length
    sort(words.begin(), words.end(), [] (const string& w1, const string& w2) {
        return w1.length() < w2.length();
    });
    unordered_map<string, int> word_map;
    word_map[words[0]] = 1;
    int res = 1;
    for (const string& s : words) {
        int curLen = helper(s, word_map);
        word_map[s] = curLen;
        res = max(res, curLen);
    }
    return res;
}