1090.Phone List

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:

Emergency 911

Alice 97 625 999

Bob 91 12 54 26

In the case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialed the first three digits of bob’s phone number. So this list would not be sonsistent.

Input

The first line of input gives a single integer, 1<=t<=40, the number of test cases. Each test starts with n, the number of phone numbers, on a separate line, 1<=n<=10000. Then follows n linss with one unique phone numbers 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 1 

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output 1

NO
YES

Their thinking ：

At first I used violence to solve problems —— Compare each phone number with the rest , Sure enough, it timed out . To solve the problem of timeout , It needs to be optimized . The optimization method is to sort all the phone numbers according to the dictionary order , Make every two phone numbers have the highest similarity , In this way, we only need to compare two adjacent phone numbers OK La ！

I first tried to use char Type two-dimensional array to store these phone numbers , But it will be troublesome when sorting , Because it is very easy to use sort Function can't be used to char Type two-dimensional array sorting ......

So you can set up an array to index each phone number , The code is as follows

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
char a[10005][11];
bool cmp(int x,int y){
	return strcmp(a[x],a[y])<0;// Sort in dictionary order 
}
int main()
{
	int n,m,i,j;
	cin>>n;
	while(n--){
		cin>>m;
		int b[m];
		for(i=0;i<m;i++){
			cin>>a[i];// Save each phone number 
			b[i]=i;//b Array for sort Index on sorting a The subscript , In this way, we can solve the problem that we can't directly a Array sorting problem 
		}
		sort(b,b+m,cmp);
		int l1=strlen(a[b[0]]);// Read the length of the phone number 
		int flag;
		for(i=0;i<m-1;i++){
			flag=0;
			int l2=strlen(a[b[i+1]]);
			for(j=0;j<min(l1,l2);j++){
				if(a[b[i]][j]!=a[b[i+1]][j]){
					flag=1;// If a phone number is a prefix of another phone number then flag=0, And vice versa 1
					break;
				}
			}
			if(flag==0){
				break;
			} 
			l1=l2;
		}
		if(flag==0)cout<<"NO"<<endl;
		else cout<<"YES"<<endl;	
	}
    return 0;
}

Of course, you don't have to char Array ,C++ Of string Isn't it fragrant? Ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
string a[10005];
bool cmp(string x,string y){
	return x<y;
}
int main()
{
	int n,m,i;
	cin>>n;
	while(n--){
		cin>>m;
		for(i=0;i<m;i++){
			cin>>a[i];
		}
		sort(a,a+m,cmp);
		int flag=0;
		for(i=0;i<m-1;i++){
			int l=min(a[i].size(),a[i+1].size());
			if(a[i].substr(0,l)==a[i+1].substr(0,l)){    //substr Is a function that intercepts strings 
				flag=1;
			}
		}
		if(flag==1)cout<<"NO"<<endl;
		else cout<<"YES"<<endl;	
	}
    return 0;
}

Does it look simple and easy to understand? Ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha