Phone Number
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
We know that if a phone number A is another phone number B’s prefix, B is not able to be called. For an example, A is 123 while B is 12345, after pressing 123, we call A, and not able to call B.
Given N phone numbers, your task is to find whether there exits two numbers A and B that A is B’s prefix.
输入
The input consists of several test cases.
The first line of input in each test case contains one integer N (0<N<1001), represent the number of phone numbers.
The next line contains N integers, describing the phone numbers.
The last case is followed by a line containing one zero.
输出
For each test case, if there exits a phone number that cannot be called, print “NO”, otherwise print “YES” instead.
示例输入
2
012
012345
2
12
012345
0
示例输出
NO
YES
提示
来源
2010年山东省第一届ACM大学生程序设计竞赛
题意：给出几个字符串问是否会有前缀产生，直接字典树搞定
1 #include <iostream>
2 #include <algorithm>
3 #include <cstring>
4 #include <cstdio>
5 using namespace std;
6 const int Max =
1000 +
10;
7 struct Node
8 {
9 int value;
10 int cnt;
11 Node * Next[
10];
12 };
13 Node *
root;
14 char str[Max];
15 bool build(
char *
s)
16 {
17 Node * p = root, *
temp;
18 int len =
strlen(s);
19 for (
int i =
0; i < len; i++
)
20 {
21 int id = str[i] -
'0';
22 if (p->Next[id] ==
NULL)
23 {
24 temp =
new Node;
25 temp->value =
id;
26 temp->cnt =
0;
27 for (
int i =
0; i <
10; i++
)
28 temp->Next[i] =
NULL;
29 p->Next[id] =
temp;
30 }
31 p = p->
Next[id];
32 if (p->
cnt)
33 return false;
34 }
35 return true;
36 }
37 void destroy(Node *
temp)
38 {
39 if (temp ==
NULL)
40 return;
41 for (
int i =
0; i <
10; i++
)
42 destroy(temp->
Next[i]);
43 delete temp;
44 }
45 int main()
46 {
47 int n;
48 while (scanf(
"%d", &n) != EOF &&
n)
49 {
50 root =
new Node;
51 for (
int i =
0; i <
10; i++
)
52 root->Next[i] =
NULL;
53 bool flag =
true;
54 while (n--
)
55 {
56 scanf(
"%s", str);
57 if (!
flag)
58 continue;
59 if (!
build(str))
60 flag =
false;
61 }
62 if (flag)
63 printf(
"YES\n");
64 else
65 printf(
"NO\n");
66 destroy(root);
67 }
68 return 0;
69 }
View Code
转载于:https://www.cnblogs.com/zhaopAC/p/5451252.html
