LeetCode 1048. 最长字符串链（哈希+DP）

示例：
输入：["a","b","ba","bca","bda","bdca"]
输出：4
解释：最长单词链之一为 "a","ba","bda","bdca"。
 
提示：
1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] 仅由小写英文字母组成。

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(),words.end(),[&](auto a, auto b){
        	return a.size() < b.size();//按长度排序
        });
        int n = words.size(), maxlen = 1, i, j, k;
        unordered_map<string, int> s;//哈希
        string tmp;
        vector<int> dp(n, 1);
        for(i = 0; i < n-1; ++i)
        {
        	s[words[i]] = i;//建立哈希
            j = i+1;
            for(k = 0; k < words[j].size(); ++k)
            {	//遍历后面长的单词，枚举所有少一个字符的子串
                tmp = words[j].substr(0,k)+words[j].substr(k+1);
                if(s.find(tmp) != s.end())//存在这个子串
                {
                    dp[j] = max(dp[j], dp[s[tmp]]+1);
                    maxlen = max(maxlen, dp[j]);
                }
            }
        }
        return maxlen;
    }
};