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".

思路：

dp[i] := max length of chain of (A[0] ~ A[i-1])

dp[i] = max{dp[j] + 1} if A[j] is prederrsor of A[i], 1 <= j <i

这里其中要求words[j]的长度要比words[i]少一，因此定义一个map(word长度--index数组)。这样每次找word[i]的predecessor时，就需要在长度为word[i].size()-1的vector中寻找就可以了，减少了寻找的次数。

代码：

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        int n = words.size();
        sort(begin(words), end(words), [](const string& a, const string& b) { 
          return a.length() < b.length();
        });
        unordered_map<int,vector<int>> map;
        for(int i=0; i<n; i++){
            map[words[i].size()].push_back(i);
        }
        
        vector<int>dp(n,1);
        dp[0] = 1;
        for(int i=1; i<n; i++){
            int l = words[i].size();
            for(auto t: map[l-1]){
                if(isPre(words[t],words[i])){
                    dp[i] = max(dp[i],dp[t]+1);
                }
            }
        }
        int ret =0;
        for(int i=0; i<n; i++){
            ret = max(ret, dp[i]);            
        }
        return ret;
    }
    bool isPre(string a, string b){
        bool flag = false;
        for(int i=0; i<a.size(); i++){
            if(flag == false){
                if(a[i] == b[i]) continue;
                else if(a[i] == b[i+1]){
                    flag = true;
                }else return false;
            }else{
                if(a[i] != b[i+1]) return false;
            }
        }
        return true;
    }
};