题解 | #最长合成字符串#

①按照长度排序
②研究第k个字符串能否由其它拼接而成（只能由其后面更短的字符串）
③每次剪切掉头部=》递归判断

class LongestString {
public:
    static bool cmp(string a,string b)
    {
        return a.size()>b.size();
    }

    //研究str能否由arr中其它字符拼接而成
    bool judge(vector<string>& arr,string str,int k)  //从第k个开始
    {
         if(str=="" )  
             return true;
        //研究第k个字符串 前面部分能否被剪切下来
        for(int i=k+1;i<arr.size();i++) //从k+1开始 因为只能由更短的拼接而成
        {
            int len=arr[i].size();
            if(arr[i]==str.substr(0,len))
            {
                //可以剪切
                if(judge(arr,str.substr(len,str.size()-len),k))  //递归判断  
                {
                    return true;
                }   
            }

        }
        return false;

    }


    int getLongest(vector<string> str, int n) {
        // write code here

       sort(str.begin(),str.end(),cmp);

        //依次从最长的那个开始 研究其能否用其它单词拼接而成
        //（即能否由更短单词拼接而成）
       for(int i=0;i<n;i++)
           if(judge(str,str[i],i))
               return str[i].size();

        return 0;
    }
};