Leetcode 720. The longest word in the dictionary

Give an array of strings words A dictionary of English . return words The longest word in , The word is created by words Other words in the dictionary gradually add a letter to form .

If there are more than one possible answer , The word with the smallest dictionary order in the answer is returned . If there is no answer , Returns an empty string .

Example 1：

 Input ：words = ["w","wo","wor","worl", "world"]
 Output ："world"
 explain ：  word "world" May by "w", "wo", "wor",  and  "worl" Gradually add a letter to form .

Example 2：

 Input ：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
 Output ："apple"
 explain ："apply"  and  "apple"  Can be composed of words in the dictionary . however  "apple"  The dictionary order of is less than  "apply" 
 

Tips ：

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 30
• All input strings words[i] All contain only lowercase letters .

Main idea ： Customize sorting first , Then define a two-dimensional array to store words with the same length
Then judge whether the length is continuous , Whether the content is incremented
Code:

class Solution {
    
public:
    static bool cmp(const string &s1,const string &s2)
    {
    
        if(s1.length()==s2.length())
            return s1<s2;
        
        return s1.length()<s2.length();
    }
    string longestWord(vector<string>& words) {
    
        sort(words.begin(),words.end(),cmp);
        int len=1;
        int maxlen=words[words.size()-1].length();
        vector<vector<string>>vec;
        
        int start_index=0;
        for(int i=1;i<=maxlen;i++)
        {
    
            bool flag=false;// Used to judge whether the length is continuous 
            bool flag2=false;// Used to determine whether the content is incremented 
            vector<string>temp;
            for(int j=start_index;j<words.size();j++)
            {
    
                
                if(words[j].length()==i)
                {
    
                    
                    flag=true;
                    //cout<<words[j]<<endl;
                    
                    if(i!=1)
                    {
    
                        vector<string>sub=vec[i-2];
                        string t=words[j].substr(0,i-1);
                        if(find(sub.begin(),sub.end(),t)!=sub.end())
                        {
    
                            // cout<<words[j]<<endl;
                            temp.push_back(words[j]);
                            flag2=true;
                        }
                    }
                    if(i==1)
                    {
    
                        flag2=true;
                        temp.push_back(words[j]);
                    }
                    
                }
                else
                {
    
                    start_index=j;
                    break;
                }
                
            }
            
            if(flag&&flag2)
            {
    
                if(i==maxlen)
                    return temp[0];
            }
            if(!flag2 || !flag )
            {
    
                
                if(vec.size())
                {
    
                    return vec[i-2][0];
                }
                else
                    return "";
            }
            else
            {
    
                vec.push_back(temp);
            }
            
        }
        
        return "";
        
    }
};