简答题 偏难
#7214

电话号码 给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如: Emergency 911 Alice 97 625 999 B…

电话号码

给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如:

Emergency 911

Alice 97 625 999

Bob 91 12 54 26

在这个例子中,我们不可能拨通Bob的电话,因为Emergency的电话是它的前缀,当拨打Bob的电话时会先接通Emergency,所以这些电话号码不是一致的。

时间限制:1000

内存限制:65536

输入

第一行是一个整数t,1 ≤ t ≤ 40,表示测试数据的数目。 每个测试样例的第一行是一个整数n,1 ≤ n ≤ 10000,其后n行每行是一个不超过10位的电话号码。

输出

对于每个测试数据,如果是一致的输出“YES”,如果不是输出“NO”。

样例输入

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

样例输出

NO
YES
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; using namespace std; int t; int n; int FLAG; // FLAG=1代表互不构成后缀,FLAG=0代表摸一个单词构成后缀 struct Node {   struct Node *next[10]; // 定义一个指针数组next,里面的元素都是Node类型的指针   int is_Cover; // 定义这个节点的访问次数   int is_End; // 定义这个节点是否是一个电话号的最后一个字符 }; void Init(Node *a) // 初始化节点i {   memset(a-&gt;next, 0, sizeof(a-&gt;next)); // next[0]~next[9]都是指针NULL   a-&gt;is_Cover = 0;   a-&gt;is_End = 0; } // 内存友好型函数:释放内存 void DELETE(Node *root) {   for (int i = 0; i &lt; 10; i++) {     if (root-&gt;next[i]) {       DELETE(root-&gt;next[i]);     } // 递归法释放内存   }   free(root); // 递归到底层,root-&gt;next[0~9]都是NULL,直接释放root即可 } void insert(Node *root, char *temp) {   Node *p = root;   int id;       // 0~9   while (*temp) // 字符串指针未到底   {     id = *temp - '0';     if (p-&gt;next[id] == NULL) {       p-&gt;next[id] = (Node *)malloc(sizeof(Node)); // 先申请内存空间       Init(p-&gt;next[id]); // 再对这个节点进行初始化     }     p = p-&gt;next[id]; // 指针往下移动     if (p-&gt;is_End) {       FLAG = 0;     } // 这个点是其他电话号的最后一个数字,包含着其他单词的前缀     p-&gt;is_Cover++;     temp++; // 字符指针向下移动   }   if (p-&gt;is_Cover &gt; 1) {     FLAG = 0;   } // 执行到这里说明temp字符串是其他长字符串的前缀,temp字符串较短   p-&gt;is_End = 1; // 设置字符串末尾标志 } int main() {   char ss[15];   cin &gt;&gt; t;   while (t--) {     Node *root = (Node *)malloc(sizeof(Node));     Init(root);     FLAG = 1; // 没有特殊情况不构成后缀     cin &gt;&gt; n;     while (n--) {       scanf("%s", ss);       if (FLAG) {         insert(root, ss);       } // 前面都没有前缀的发生,可以继续插入     }     if (FLAG == 0) {       cout &lt;&lt; "NO" &lt;&lt; endl;     } else {       cout &lt;&lt; "YES" &lt;&lt; endl;     }     DELETE(root); // 释放内存   }   return 0; }</pre>
这道题暂未补解析。