Phone List

Problem Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:
1. Emergency 911
2. Alice 97 625 999
3. Bob 91 12 54 26
In
this case, it’s not possible to call Bob, because the central would
direct your call to the emergency line as soon as you had dialled the
first three digits of Bob’s phone number. So this list would not be
consistent.

Input

The
first line of input gives a single integer, 1 <= t <= 40, the
number of test cases. Each test case starts with n, the number of phone
numbers, on a separate line, 1 <= n <= 10000. Then follows n
lines with one unique phone number on each line. A phone number is a
sequence of at most ten digits.

Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

Sample Input

911

97625999

91125426

113

12340

123440

12345

98346

Sample Output

YES

//排序比较相邻的字符串是否包含， time:156 ms;

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <iomanip>

 #include <cstdlib>

 using namespace std;

 const int INF=0x5fffffff;

 const int MS=;

 const double EXP=1e-;

 char str[MS][];

 int cmp(const void *a,const void *b)

 {

     return strcmp((char *)a,(char *)b);

 }

 int main()

 {

     int T;

     int n,i;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&n);

         for(i=;i<n;i++)

             scanf("%s",str[i]);

         //sort(str,str+n,cmp);

         qsort(str,n,sizeof(str[]),cmp);

         int ok=;

         for(i=;i<n&&ok;i++)

         {

             if(strncmp(str[i-],str[i],strlen(str[i-]))==)

                 ok=;

         }

         if(ok)

             puts("YES");

         else

             puts("NO");

     }

     return ;

 }

// 静态 Trie 树法 time 78 ms

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <vector>

 #include <stack>

 #include <queue>

 #include <set>

 #include <map>

 #include <iomanip>

 #include <cstdlib>

 using namespace std;

 const int INF=0x5fffffff;

 const int MS=;

 const double EXP=1e-;

 struct node

 {

     bool have;

     node * next[];

 }nodes[MS];

 node *root;

 bool flag;

 int cnt;

 node * add_node(int c)

 {

     node *p=&nodes[c];

     for(int i=;i<;i++)

         p->next[i]=NULL;

     p->have=false;

     return p;

 }

 void insert(char *str)

 {

     node *p=root,*q;

     int len=strlen(str);

     for(int i=;i<len;i++)

     {

         int id=str[i]-'';

         if(p->next[id]==NULL)

         {

             q=add_node(cnt++);

             p->next[id]=q;

         }

        // if(p->have==true)

        //     flag=true;

         p=p->next[id];

         if(p->have==true)

             flag=true;

     }

     p->have=true;

     for(int i=;i<;i++)

     {

         if(p->next[i]!=NULL)

         {

             flag=true;

             break;

         }

     }

 }

 int main()

 {

     int i,n,t;

     char str[];

     scanf("%d",&t);

     while(t--)

     {

         cnt=;

         root=add_node(cnt++);

         flag=false;

         scanf("%d",&n);

         for(i=;i<n;i++)

         {

             scanf("%s",str);

             if(!flag)

             {

                 insert(str);

             }

         }

         if(flag==false)

             printf("YES\n");

         else

             printf("NO\n");

     }

     return ;

 }

随机推荐

PHP realpath() 函数
定义和用法 realpath() 函数返回绝对路径. 该函数删除所有符号连接(比如 '/./', '/../' 以及多余的 '/'),返回绝对路径名. 若失败,则返回 false.比如说文件不存在的话 ...
【leedcode】 Longest Palindromic Substring
Given a , and there exists one unique longest palindromic substring. https://leetcode.com/problems/l ...
UITabBarController加载之后不显示sub view controller
原代码: fileprivate func createSubiewControllers() { let newsVC = NewsViewController() let newsItem = U ...
Python中strip()函数
在python API中这样解释strip()函数:
HTML5 Canvas核心技术—图形、动画与游戏开发&period;pdf2
事件处理: HTML5应用程序是以事件来驱动的,可以在canvas中增加一个事件监听器,当事件发生时,浏览器就会调用这个监听器 //方法一canvas.onmousedown=function(e){ ...
how to count uv area
先放着,空了再整理.... fn getModeUvVolumetric mode chang= ----得到UV使用率( --global facesNumSum = meshop.getnumfa ...
Session变量不能转移到下页&period;解决&colon; session&period;use&lowbar;trans&lowbar;sid = 1
附:文摘 ============================================================ 在PHP使用SESSION的朋友可能会碰到这么一个问题.SESSIO ...
iOS基础 - NSURLSession
使用URLSession所有的网络访问都是有缓存的,缓存文件自动保存在tmp文件夹中,URLSession本身实现的时候,就是少量多次的! l 使用defaultSessionConfiguratio ...
Markdown引用本地图片语法
Markdown引用本地图片语法 markdown引用图片标准方式如下: ![Alt text](/path/to/img.jpg) 测试markdown文本如下: # 测试相对路径图片 ![Alt ...
hdu 5573Binary Tree
Binary Tree Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Tota ...

随机推荐

相关文章