1048. Longest String Chain

這題我一開始以為單純只要字母多一個就可以做串聯, 但不是單單字母多一個即可, 是這個字母是插入原本的字串

舉例

ab -> adb 這是合格的, d插到ab的中間
ab -> bda 字母數量跟上面一樣, 但這是不合格的

所以我們就是用unordered_map, 做字串的儲存, 並且後面就是鏈結的最大值,

一旦可以找到一個插入前的字串, 我們就取那個字串的值加一, 看是否能找到更長的鏈結

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        sort(words.begin(), words.end(), [](string &a, string &b){
            return a.size() < b.size();
        });
        unordered_map<string, int> dp;
        int res = 0;
        for(string s: words){
            for(int i = 0; i < s.size() ;i++){
                string pre = s.substr(0, i) + s.substr(i + 1);
                if(dp.count(pre)){
                    dp[s] = max(dp[s], dp[pre] + 1);
                }else{
                    dp[s] = max(dp[s], 1);
                }
          
            }
         
            res = max(res, dp[s]);
        }
   
        return res;
    }
};