leetcode 1048. Longest String Chain

Seawolf

1. Given a list of words, each word consists of English lowercase letters.
   
2. 
   
3. 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".
   
4. 
   
5. 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.
   
6. 
   
7. Return the longest possible length of a word chain with words chosen from the given list of words.
   
8. 
   
9. 
   
10. 
    
11. Example 1:
    
12. 
    
13. Input: ["a","b","ba","bca","bda","bdca"]
    
14. Output: 4
    
15. Explanation: one of the longest word chain is "a","ba","bda","bdca".
    
16. 
    
17. 
    
18. Note:
    
19. 
    
20. 1 <= words.length <= 1000
    
21. 1 <= words[i].length <= 16
    
22. words[i] only consists of English lowercase letters.

复制代码

1. class Solution {
   
2. public:
   
3.     int longestStrChain(vector<string>& words) {
   
4.         if(words.size() == 0) return 0;
   
5.         sort(words.begin(),words.end(),cmp);
   
6.         vector <int> dp(words.size(),0);
   
7.         dp[0] = 1;
   
8.         int Max = 1;
   
9.         for(int i = 1; i< words.size();i++){
   
10.             int local = 0;
    
11.             for(int j = 0 ; j < i ; j++){
    
12.                 if(words[i].size() - words[j].size() == 1 && isPredecessor(words[j], words[i])){   
    
13.                     local = max(local, dp[j]);
    
14.                 }
    
15.                
    
16.             }
    
17.             dp[i] = local +1;
    
18.             
    
19.             Max = max(Max, dp[i]);
    
20.         }
    
21.         
    
22.         
    
23.         return Max;
    
24.     }
    
25. 
    
26. private:
    
27.     static bool cmp (const string &a, const string &b){
    
28.         return a.size() < b.size();
    
29.     }
    
30.    
    
31.     int isPredecessor(string a, string b){
    
32.         sort(a.begin(),a.end());
    
33.         sort(b.begin(),b.end());
    
34.         int count = 0;
    
35.         int i = 0, j = 0;
    
36.         while(i != a.size() && j != b.size()){
    
37.             if(a[i] != b[j]){
    
38.                 j++;
    
39.                 count++;
    
40.             }
    
41.             else{
    
42.                 i++;
    
43.                 j++;
    
44.             }
    
45.         }
    
46.         if(count == 0 && i == a.size() && j != b.size()) return 1;
    
47.         if(count == 1) return 1;
    
48.         else return 0;
    
49.         
    
50.     }
    
51.    
    
52.    
    
53. };

复制代码