leetcode 472. 连接词

 1  const int N=1e5+5;
 2 class Solution {
 3 public:
 4     int ch[N][26];
 5     vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
 6         unordered_map<int,int>mp;
 7         sort(words.begin(),words.end(),[&](string &a,string &b){return a.size()<b.size();});
 8         vector<string>ans;
 9         int tot=0;
10         memset(ch,0,sizeof(ch));
11         function<void(string &s)>insert=[&](string &s)
12         {
13             int x=0;
14             for(auto &p:s)
15             {
16                 if(!ch[x][p-'a'])ch[x][p-'a']=++tot;
17                 x=ch[x][p-'a'];
18             }
19             mp[x]=1;
20         };
21         function<int(string &,int,int ,int )>check=[&](string &s,int u,int n,int cnt)
22         {
23             if(u==n)
24             {
25                 if(cnt>1)return 1;
26                 else return 0;
27             }
28             int x=0,sz=s.size();
29             for(int i=u;i)
30             {
31                 x=ch[x][s[i]-'a'];
32                 if(!x)return 0;
33                 if(mp[x])
34                 {
35                     if(check(s,i+1,n,cnt+1))return 1;
36                 }
37             }
38             return 0;
39         };
40         for(auto &p:words)
41         {
42             int sz=p.size();
43             if(check(p,0,sz,0))ans.push_back(p);//这里不要insert，可以证明c=a+b d=c+x=a+b+x，如果插入的话，判断会从c。end又搜一遍；
44             else insert(p);
45         }
46         return ans;
47     }
48 };