#10049. 「一本通 2.3 例 1」Phone List

字典树板子题

#include<iostream>
#include <algorithm>
#include <cstring>
using namespace std;
 const int N=1e5+4;
 char num[40];
 int len,fg;
 int ch[N][15],tot,val[N];
 void insert(char *s){
     int i,u=1;
     
     for(i=0;i<len;i++){
         int c=s[i]-'0';
         if(ch[u][c]==0){
             ch[u][c]=++tot; 
         }
         else if(i==len-1) fg=0;
         u=ch[u][c];
         if(val[u]) fg=0;
     }
     val[u]=1;
 }
 
 main(){
     int i,cas; cin>>cas;
     while(cas--){
         fg=1; tot=1; 
         memset(ch,0,sizeof ch);
         memset(val,0,sizeof val);
         
      int tes; cin>>tes;
      for(i=1;i<=tes;i++){
          cin>>num,len=strlen(num); insert(num);
      }
      if(fg) cout<<"YES"; else cout<<"NO";
      cout<<endl;
    }
 }