leetcode 1048. Longest String Chain

Seawolf

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

Note:

1 <= words.length <= 1000
1 <= words[i].length <= 16
words[i] only consists of English lowercase letters.

class Solution {
public:
    int longestStrChain(vector<string>& words) {
        if(words.size() == 0) return 0;
        sort(words.begin(),words.end(),cmp);
        vector <int> dp(words.size(),0);
        dp[0] = 1;
        int Max = 1;
        for(int i = 1; i< words.size();i++){
            int local = 0;
            for(int j = 0 ; j < i ; j++){
                if(words[i].size() - words[j].size() == 1 && isPredecessor(words[j], words[i])){    
                    local = max(local, dp[j]);
                }
                
            }
            dp[i] = local +1;
            
            Max = max(Max, dp[i]);
        }
        
        
        return Max;
    }

private:
    static bool cmp (const string &a, const string &b){
        return a.size() < b.size();
    }
    
    int isPredecessor(string a, string b){
        sort(a.begin(),a.end());
        sort(b.begin(),b.end());
        int count = 0;
        int i = 0, j = 0;
        while(i != a.size() && j != b.size()){
            if(a[i] != b[j]){
                j++;
                count++;
            }
            else{
                i++;
                j++;
            }
        }
        if(count == 0 && i == a.size() && j != b.size()) return 1;
        if(count == 1) return 1;
        else return 0;
        
    }
    
    
};