Phone List HDU1671 字典树Trie

模板题...不过会爆内存,要小心
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string.h>
 4 #pragma warning ( disable : 4996 )
 5 using namespace std;
 6 
 7 const int inf = 0x3f3f3f3f;
 8 const int maxn = 10;
 9 
10 char t[12];
11 bool flag;
12 
13 struct node {
14     bool end;
15     node* next[maxn];
16     node()
17     {
18         end = false;
19         memset( next, NULL, sizeof(next) );
20     }
21 }*r;
22 
23 void create( node* root )
24 {
25     int len = strlen(t);
26 
27     for ( int i = 0; i < len; i++ )
28     {
29         int tmp = t[i]-'0';
30         if ( root->next[tmp] == NULL )
31         {
32             node* next = new node;
33 
34             root->next[tmp] = next;
35         }
36 
37         root = root->next[tmp];
38         if(root->end) flag = false;
39     }
40     root->end = true;
41     for( int i = 0; i < maxn; i++ )
42         if( root->next[i] != NULL ) 
43             flag = false;
44 }
45 
46 void del( node* root )
47 {
48     if( root == NULL ) return;
49     for( int i = 0; i < maxn; i++ )
50         del(root->next[i]);
51     free(root);
52 }
53 
54 
55 int main()
56 {
57     int all;
58     cin >> all;
59     while (all--)
60     {
61         flag = true;
62         int n;
63         cin >> n;
64 
65         r = new node();
66          
67         for ( int i = 1; i <= n; i++ )
68         {
69             scanf( "%s", t );
70             if(flag)
71                 create(r);
72         }
73 
74         del(r);
75 
76         if(flag)
77             cout << "YES" << endl;
78         else
79             cout << "NO" << endl;
80 
81     }
82     return 0;
83 }
View Code