leetcode 1048

题目：

给出一个单词数组 words ，其中每个单词都由小写英文字母组成，如果我们可以不改变其他字符的顺序 ，在wordA 的任何地方添加 恰好一个 字母使其变成wordB，那么我们认为wordA是wordB的前身。例如”abc”是”abac”的前身，而”cba”不是”bcad”的前身。词链式单词[word_1,word_2, …, word_k]组成的序列，k>=1，其中word1是word2的前身，word2是word3的前身，依此类推。一个单词通常是k==1的单词链，从给定单词列表words中选择单词组成词链，返回词链的最长可能长度

输入输出

示例1：

输入：words = [“a”,”b”,”ba”,”bca”,”bda”,”bdca”]
输出：4
解释：最长单词链之一为 [“a”,”ba”,”bda”,”bdca”]

示例2:

输入：words = [“xbc”,”pcxbcf”,”xb”,”cxbc”,”pcxbc”]
输出：5
解释：所有的单词都可以放入单词链 [“xb”, “xbc”, “cxbc”, “pcxbc”, “pcxbcf”].

示例3:

输入：words = [“abcd”,”dbqca”]
输出：1
解释：字链[“abcd”]是最长的字链之一。[“abcd”，”dbqca”]不是一个有效的单词链，因为字母的顺序被改变了。

提示：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] 仅由小写英文字母组成

思路

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int longestStrChain(vector<string> &words)
    {
        // 首先对words进行排个序，按照长度排序
        sort(words.begin(), words.end(), [](const auto &a, const auto &b)
             { return a.length() < b.length(); });
        int ans = 0;
        unordered_map<string, int> mp;
        for (auto &s : words)
        {
            int res = 0;
            for (int i = 0; i < s.length(); ++i)
            {
                auto it = mp.find(s.substr(0, i) + s.substr(i + 1));
                if (it != mp.end())
                {
                    res = max(res, it->second);
                }
            }
            ans = max(ans, mp[s] = res + 1);
        }
        return ans;
    }
};