Seawolf 发表于 2019-10-18 13:24:37

leetcode 1048. Longest String Chain

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 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.length <= 16
words 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 = 1;
      int Max = 1;
      for(int i = 1; i< words.size();i++){
            int local = 0;
            for(int j = 0 ; j < i ; j++){
                if(words.size() - words.size() == 1 && isPredecessor(words, words)){   
                  local = max(local, dp);
                }
               
            }
            dp = local +1;
            
            Max = max(Max, dp);
      }
      
      
      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 != b){
                j++;
                count++;
            }
            else{
                i++;
                j++;
            }
      }
      if(count == 0 && i == a.size() && j != b.size()) return 1;
      if(count == 1) return 1;
      else return 0;
      
    }
   
   
};
页: [1]
查看完整版本: leetcode 1048. Longest String Chain