1129. Longest String Chain

• Difficulty: Medium

• Topics: Hash Table, Dynamic Programming

• Similar Questions:

Problem:

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.

Solutions:

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        if (words.size() == 0)  return 0;
        auto comparator = [](const string& word1, const string& word2) {
            return word1.length() < word2.length();
        };

        int ret = 0;
        unordered_map<string, int> dp = {};
        sort(words.begin(), words.end(), comparator);
        int pos = 0;
        for (int len = 1; len <= words.back().length(); ++len) {
            unordered_map<string, int> temp;
            while (pos < words.size() && words[pos].length() == len) {
                string word = words[pos];
                temp[word] = 1; // this initializaiton is very important!
                for (auto& entry : dp) {
                    if (isPredecessor(entry.first, word)) {
                        temp[word] = max(temp[word], 1 + entry.second);
                    }
                }
                ret = max(ret, temp[word]);
                // update pos
                ++pos;
            }
            swap(dp, temp);
        }

        return ret;
    }

private:
    bool isPredecessor(const string& str1, const string& str2) {
        int pos = 0;
        while (pos < str1.length() && str1[pos] == str2[pos]) ++pos;
        if (pos == str1.length())   return true;
        while (pos < str1.length() && str1[pos] == str2[pos + 1]) ++pos;
        return pos == str1.length();
    }

};