[Google] LeetCode 1048 Longest String Chain

You are given an array of words where each word consists of lowercase English letters.

\(word_A\) is a predecessor of \(word_B\) if and only if we can insert exactly one letter anywhere in \(word_A\) without changing the order of the other characters to make it equal to \(word_A\).

For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".
A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Solution

我们用 \(map\) 来定义 \(dp\) 数组。现将原来的序列排序，得到长度从小到大的序列。

定义 \(dp[s]\) 表示以 \(s\) 结尾的最长 word chain 长度，考虑如何转移：

其中 \(s'\) 为 \(s\) 的前驱。这里用 \(erase\) 函数，我们遍历当前的串 \(s\), 看删去一个位置后得到的 \(s'\) 是否在 \(map\) 中

class Solution {
private:
    map<string, int> dp;
    int ans = INT_MIN;
public:
    int longestStrChain(vector<string>& words) {
        int n = words.size();
        sort(words.begin(), words.end(),
            [](string& s1, string& s2){return s1.size()<s2.size();});
        for(int i=0;i<n;i++){
            dp[words[i]]=1;
            for(int j=0;j<words[i].size();j++){
                string tmp = words[i];
                tmp.erase(tmp.begin()+j);
                if(dp[tmp])dp[words[i]] = max(1+dp[tmp], dp[words[i]]);
            }
            ans = max(ans, dp[words[i]]);
        }
        return ans;
    }
};